هیپ برای انتخاب Top-K
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, recognize repeated access to an extreme value and bounded top-k selection; compare a heap with sorting when complete order is required.
- Introduce the min-heap property and Python heapq operations without teaching heap implementation from scratch.
- Independently choose which candidate must remain at the root when retaining the k closest points to the origin.
- Develop K Closest Points to Origin from repeatedly selecting minima and full sorting to a size-k heap of negated squared distances.
- Use comparable tuple entries and avoid unnecessary square roots; implement the Python solution under an arbitrary-output-order contract.
- Prove that the heap retains the best k candidates seen so far; derive O(n log(k + 1)) time, O(k) auxiliary space, and the O(n) heapify construction bound.
- Test ties, repeated points, k equal to zero or n when permitted, and invalid k under the agreed contract; diagnose reversed priority signs and claims that heap iteration is sorted.
بهترین نامزدها، نه ترتیب کامل
**قرارداد انتخاب**
نقطهها: \((x,y)\in\mathbb{Z}^2\)؛ تعداد: \(n\)
\(k\in\mathbb{Z},\quad 0\le k\le n\)
خروجی نامرتب؛ تساوی در مرز: هر انتخاب معتبر؛ تکرارها: ورودیهای جدا.
**فاصله بدون جذر**
\[d^2=x^2+y^2\]
\[(1,1):\quad 1^2+1^2=2\]
\[(3,0):\quad 3^2+0^2=9\]
\(2<9\): نقطهٔ \((1,1)\) نزدیکتر است.
**Brute Force**
برای هر انتخاب، جستوجوی همهٔ نامزدهای باقیمانده.
\[O(nk)\]
**sorting**
مرتبسازی همه با فاصلهٔ مربع؛ برداشتن \(k\) عضو اول.
\[O(n\log n)\]
**bounded top-k selection**
فقط بهترین \(k\) نامزد را میخواهیم؛ نه ترتیب کامل همهٔ \(n\) نقطه را.
**دلیل انتخاب ابزار**
نیاز مکرر به کوچکترین یا بزرگترین عضو ← بررسی heap
نیاز به ترتیب کامل خروجی ← sorting
دیدن \(k\) بهتنهایی دلیل انتخاب heap نیست.
تضمین ریشه و ابزارهای heapq
```svg
<svg viewBox="0 0 800 550" xmlns="http://www.w3.org/2000/svg"><text x="180" y="30" class="tm-text" font-size="22" text-anchor="middle">min-heap</text><path d="M180 85 L100 155 M180 85 L260 155" class="tm-line" fill="none"/><circle cx="180" cy="80" r="28" class="tm-accent"/><circle cx="100" cy="165" r="28" class="tm-soft"/><circle cx="260" cy="165" r="28" class="tm-soft"/><text x="180" y="88" class="tm-text" font-size="24" text-anchor="middle">1</text><text x="100" y="173" class="tm-text" font-size="24" text-anchor="middle">4</text><text x="260" y="173" class="tm-text" font-size="24" text-anchor="middle">2</text><text x="180" y="228" class="tm-text-accent" font-size="18" text-anchor="middle" direction="rtl">کوچکترین عضو در ریشه</text><rect x="65" y="250" width="230" height="48" rx="10" class="tm-soft"/><text x="180" y="282" class="tm-text" font-size="24" text-anchor="middle">[1, 4, 2]</text><text x="180" y="325" class="tm-text-gold" font-size="18" text-anchor="middle" direction="rtl">فهرست داخلی؛ نه فهرست مرتب</text><rect x="370" y="35" width="390" height="290" rx="14" class="tm-surface"/><text x="565" y="70" class="tm-text" font-size="22" text-anchor="middle">Python · heapq · list</text><text x="395" y="115" class="tm-text-accent" font-size="20">heap[0]</text><text x="735" y="145" class="tm-text2" font-size="17" text-anchor="end" direction="rtl">خواندن ریشه؛ زمان ثابت؛ heap غیرخالی</text><text x="395" y="190" class="tm-text" font-size="20">heappush</text><text x="735" y="190" class="tm-text2" font-size="17" text-anchor="end" direction="rtl">افزودن عضو</text><text x="395" y="235" class="tm-text" font-size="20">heappop</text><text x="735" y="235" class="tm-text2" font-size="17" text-anchor="end" direction="rtl">حذف و بازگرداندن کمینه</text><text x="565" y="290" class="tm-text-accent" font-size="18" text-anchor="middle" direction="rtl">هزینهٔ هر عملیات: لگاریتم اندازهٔ heap</text><rect x="40" y="350" width="720" height="80" rx="12" class="tm-soft"/><text x="175" y="377" class="tm-text" font-size="17" text-anchor="middle">heappush(heap, 0)</text><text x="175" y="410" class="tm-text-accent" font-size="22" text-anchor="middle">[0, 1, 2, 4]</text><text x="385" y="400" class="tm-text2" font-size="26" text-anchor="middle">→</text><text x="575" y="377" class="tm-text" font-size="17" text-anchor="middle">heappop(heap)</text><text x="575" y="410" class="tm-text-accent" font-size="20" text-anchor="middle" direction="rtl">[1, 4, 2]؛ خروجی: 0</text><text x="65" y="475" class="tm-text" font-size="20">heappushpop</text><text x="735" y="475" class="tm-text2" font-size="18" text-anchor="end" direction="rtl">افزودن، سپس حذف کمینه؛ یکجا</text><text x="65" y="520" class="tm-text" font-size="20">heapify</text><text x="735" y="520" class="tm-text2" font-size="18" text-anchor="end" direction="rtl">تبدیل list به heap؛ زمان خطی</text></svg>
```
ریشه، بدترین نامزدِ نگهداشتهشده
نگهداشتن نزدیکترین نقطهها با یک min-heap محدود
**کدام نامزد باید حذف شود؟**
\[ k=2 \]
با ورود نقطهٔ بهتر، دورترین نامزد باید حذف شود؛ نه نزدیکترین.
**تبدیل فاصله به اولویت**
\[ d^2=x^2+y^2,\qquad p=-d^2\qquad\Longrightarrow\qquad \min p=-\max d^2 \]
ریشهٔ min-heap: دورترین نامزدِ نگهداشتهشده.
**ورود نقطهٔ اول؛ هنوز جا داریم**
\[ (1,1):\quad d^2=1^2+1^2=2,\quad p=-2\qquad H=[-2] \]
**ورود نقطهٔ دوم؛ ظرفیت پر میشود**
\[ (3,0):\quad d^2=3^2+0^2=9,\quad p=-9\qquad H=[-9,-2] \]
ریشه مربوط به نقطهٔ \((3,0)\) است.
**ورود نقطهٔ سوم**
\[ (0,2):\quad d^2=0^2+2^2=4,\quad p=-4 \]
**حذف با heappushpop**
\[ \min\{-2,-9,-4\}=-9\qquad\Longrightarrow\qquad H=[-4,-2] \]
نقطهٔ \((3,0)\) حذف میشود.
**نامزدهای باقیمانده**
\[ \{(1,1),(0,2)\},\qquad d^2\in\{2,4\} \]
دو نقطهٔ نزدیکتر باقی میمانند.
**invariant بعد از هر ورود**
\[ |H|=\min(k,t) \]
\(t\): تعداد نقطههای دیدهشده. پیش از پرشدن ظرفیت، همه را داریم؛ پس از آن، دقیقاً \(k\) تا از نزدیکترینها را داریم. شروع: خالی. جا داریم: اضافه میکنیم. جا نداریم: دورترین را حذف میکنیم. هر نقطهٔ حذفشده، همان موقع به تعداد کافی نامزدِ بهتر یا همفاصله داشته است؛ پس دوباره لازم نمیشود.
پیادهسازی و قرارداد فاصلههای برابر
```python
from heapq import heappush, heappushpop
def kclosest(points, k):
if k < 0 or k > len(points):
raise ValueError
if k == 0:
return []
heap = []
for i, (x, y) in enumerate(points):
d = x * x + y * y
entry = (-d, i)
if len(heap) < k:
heappush(heap, entry)
else:
heappushpop(heap, entry)
return [points[i] for _, i in heap]
```
- **مقایسهٔ tuple:** ابتدا اولویت، سپس اندیس؛ بدون مقایسهٔ شیءهای نقطه.
- **فاصلهٔ برابر:** حذف ورودی زودتر مجاز است؛ نقطههای تکراری اندیسهای جدا دارند.
- **قرارداد خروجی:** بدون sort؛ پس از هر دور \(\lvert\mathrm{heap}\rvert \le k\).
هزینهها و آزمون قرارداد انتخاب
**هزینه تابع اندازهٔ heap است**
برای هر نقطه: \(O(\log(k+1))\)
زمان کل برای \(k\ge 1\): \(O(n\log(k+1))\)
برای \(k=0\): زمان \(O(1)\)
حافظهٔ کمکی: \(O(k)\)؛ خروجی: \(k\) عضو
با فرض هزینهٔ ثابت محاسبات مختصات و مقایسهٔ عددها
**شروع با heapify**
برگها: حدود \(k/2\)، بدون حرکت
حداکثر یک سطح حرکت: حدود \(k/4\)
\(\displaystyle \sum_{h\ge 0}\frac{k}{2^{h+1}}h=O(k)\)
ساخت اولیه خطی است؛ برای کد ما ضروری نیست.
**تساوی فاصله، نه حذف تکرار**
ورودی: \((1,0),\;(-1,0),\;(1,0)\)؛ \(k=2\)
هر سه: \(d^2=1\)
انتخاب هر دو ورودی معتبر است؛ حتی دو نقطهٔ هممختصات.
**آزمون مرزهای قرارداد**
\(k=0\): خروجی خالی؛ ورودی خالی هم معتبر است.
\(k=n\): همهٔ ورودیها با تعداد تکرار درست؛ نه لزوماً مرتب.
\(k<0\) یا \(k>n\): خطای ValueError
**آزمون علامت و درستی خروجی**
اولویت مثبت در min-heap: با ورود \(d^2=4\)، نامزد با \(d^2=2\) حذف میشود؛ یعنی حذف نامزد بهتر!
معیار آزمون: تعداد، تکرارها و نزدیکترینبودن؛ نه ترتیب list.
**heap همیشه برنده نیست**
\(k=n\): فقط برگرداندن همهٔ ورودیها کافی است.
Quickselect: میانگین زمان خطی
مسیر مصاحبه: قرارداد ← راه ساده ← انتخاب الگو ← کد ← تست
بازگشت به دوره