Chapterبەش 3 · Lectureوانە 3.2
Priority Queues and Heapsکیووە پێشینەییەکان و هیپەکان
Why greedy best-first search and A* need a priority queue, how a min-heap keeps the smallest item at the top, how it is stored in a list with simple index rules, how sift-up and sift-down work (with the Lab 3 drawing corrected), and how to use Python's heapq with (priority, count, item) tuples.
بۆچی و A* پێویستیان بە هەیە، چۆن بچووکترین دانە لە سەرەوە دەهێڵێتەوە، چۆن بە یاسای سادەی لە هەڵدەگیرێت، و چۆن کار دەکەن (لەگەڵ ڕاستکردنەوەی وێنەکەی تاقیگەی ٣) و چۆن heapqـی بە (priority, count, item) بەکار دێت.
What you will learnچی فێر دەبیت
- Explain what a priority queue is and why informed search needs one.
- Define min-heap and max-heap correctly and recognise a valid heap.
- Find parents and children in a heap list with (i − 1) // 2, 2i + 1 and 2i + 2.
- Carry out sift-up and sift-down by hand.
- Use heapq with (priority, count, item) tuples and fix the lab's heapq bugs.
- ڕوونی بکەیتەوە چییە و بۆچی پێویستی پێیەتی.
- و بە دروستی پێناسە بکەیت و دروست بناسیتەوە.
- باوک و منداڵەکان لە بە (i − 1) // 2، 2i + 1 و 2i + 2 بدۆزیتەوە.
- و بە دەست ئەنجام بدەیت.
heapqبە (priority, count, item) بەکار بهێنیت وheapqـی تاقیگەکە چاک بکەیتەوە.
Why a priority queue?بۆچی کیووی پێشینەیی؟
Lab 3 starts with two keywords: priority queue and heap (min-heap and max-heap). Here is why. Breadth-first search takes the oldest place from its frontier, and depth-first search takes the newest. Smarter searches such as Greedy best-first search and A* search always take the most promising place: the one with the smallest estimated distance or cost. So the frontier must hand out its smallest value first, every time. A structure that does this is a priority queue, and the usual way to build one is a min-heap. (An ordinary queue serves items in the order they arrive: see Queues in computing.)
تاقیگەی ٣ بە دوو وشەی سەرەکی دەست پێدەکات: و ( و ). هۆکارەکەی ئەمەیە. کۆنترین شوێن لە دەبات و نوێترین. گەڕانە زیرەکترەکانی وەک گەڕانی چاوچنۆکانە و گەڕانی A* هەمیشە هیوابەخشترین شوێن دەبەن: ئەوەی بچووکترین دووری یان تێچووی مەزەندەکراوی هەیە. کەواتە دەبێت هەموو جارێک بچووکترین نرخەکەی پێش هەموو ئەوانی تر بداتەوە. پێکهاتەیەک کە ئەمە دەکات ـە و ڕێگا باوەکەی دروستکردنی ـە. ( ئاسایی دانەکان بە ڕیزی گەیشتنیان دەداتەوە: بڕوانە کیووەکان لە کۆمپیوتەردا.)
A queue in which every item has a priority, and the item with the best (usually lowest) priority value always comes out first. Greedy best-first search and A* use one.
کە هەر دانەیەکی پێشینەییەکی هەیە و هەمیشە ئەو دانەیەی باشترین (زۆرجار کەمترین) نرخی پێشینەیی هەیە یەکەم جار دەردەچێت. و بەکاری دەهێنن.
In a hospital emergency room, patients are not seen in the order they arrive. A nurse gives each one a priority, and the most urgent patient goes in first, even if they came last. A priority queue works the same way: every item has a priority number, and the item with the best (smallest) number comes out first.
لە بەشی فریاکەوتنی نەخۆشخانەیەکدا، نەخۆشەکان بە ڕیزی هاتنیان نابینرێن. پەرستارێک پێشینەییەک دەدات بە هەر یەکێکیان و نەخۆشی هەرە بەپەلە یەکەم دەچێتە ژوورەوە، تەنانەت ئەگەر دوایین کەس بووبێت کە هاتووە. بە هەمان شێوە کار دەکات: هەر دانەیەک ژمارەیەکی پێشینەیی هەیە و ئەو دانەیەی باشترین (بچووکترین) ژمارەی هەیە یەکەم دەردەچێت.
Where the analogy stops workingسنووری ئەم نموونەیە
When two patients are equally urgent, the nurse may take the one who came first. A heap does not do that by itself: you add a counter, as shown later in this lesson.
کاتێک دوو نەخۆش وەک یەک بەپەلەن، پەرستارەکە لەوانەیە ئەوەیان بەرێت کە یەکەم هاتووە. خۆی ئەمە ناکات: زیاد دەکەیت، وەک لە دواتری ئەم وانەیەدا پیشان دەدرێت.
What a heap isهیپ چییە
A tree-shaped data structure that always keeps the smallest item (min-heap) or the largest item (max-heap) at the top, so it can be taken out quickly; it is the normal way to build a . In databases, a heap (heap file) is a table whose rows are stored in no particular order, without a .
دارئاسایە کە هەمیشە بچووکترین دانە () یان گەورەترین دانە () لە سەرەوە دەهێڵێتەوە، بۆیە بە خێرایی دەردەهێنرێت؛ ڕێگەی ئاساییە بۆ دروستکردنی . لە ، هیپ (فایلی هیپ) خشتەیەکە کە ڕیزەکانی بە هیچ ڕیزبەندییەک هەڵنەگیراون و نییە.
A heap is a special tree-based data structure with two properties:
تایبەتی دارئاسایە کە دوو تایبەتمەندیی هەیە:
- Ordered. In a min-heap every parent is smaller than or equal to its children, so the root holds the smallest value. In a max-heap every parent is larger than or equal to its children, so the root holds the largest value.
- Complete. It is a complete binary tree (see the next screen).
- ڕیزکراو. لە هەموو باوکێک لە منداڵەکانی بچووکترە یان یەکسانە، بۆیە بچووکترین نرخ هەڵدەگرێت. لە هەموو باوکێک لە منداڵەکانی گەورەترە یان یەکسانە، بۆیە گەورەترین نرخ هەڵدەگرێت.
- تەواو. (بڕوانە لاپەڕەی داهاتوو).
| Propertyتایبەتمەندی | Min-heap | Max-heap |
|---|---|---|
| Ruleیاسا | parent ≤ childrenباوک ≤ منداڵەکان | parent ≥ childrenباوک ≥ منداڵەکان |
| Root | the smallest valueبچووکترین نرخ | the largest valueگەورەترین نرخ |
| Example (level by level)نموونە (ئاست بە ئاست) | 1; 3, 2; 4, 6, 5 | 6; 5, 3; 4, 2, 1 |
| Used forبەکاردێت بۆ | greedy best-first search, A*, Python's heapq، A*، heapqـی | “always give me the biggest”«هەمیشە گەورەترینم بدەرێ» |
Notice: a heap is not fully sorted. In the min-heap 1; 3, 2 the right child 2 is smaller than the left child 3, and that is allowed. Only each parent and its own children are compared. This partial order is cheaper to keep than a full sort, and it is enough to find the minimum instantly.
تێبینی: بە تەواوی ڕیز نەکراوە. لە 1; 3, 2 منداڵی ڕاست (2) لە منداڵی چەپ (3) بچووکترە و ئەمە ڕێگەپێدراوە. تەنها هەر باوکێک لەگەڵ منداڵەکانی خۆیدا بەراورد دەکرێت. هێشتنەوەی ئەم ڕیزبەندییە نیوەییە لە تەواو هەرزانترە و بەسە بۆ دۆزینەوەی بچووکترین بە یەکسەر.
Min-heaps: parent no larger than its children, storing the tree in a list, and how sift up and sift down repair the order.
: لە خۆی گەورەتر نییە، لە هەڵدەگیرێت، هەروەها چۆن و ڕیزبەندییەکە چاک دەکەنەوە.
Watch 1:04-3:10: heap rules, min and max heaps, and storing the tree in a list (next screen).
لە 1:04 تا 3:10 سەیر بکە: یاساکانی ، و . هەروەها هەڵگرتنی لە (شاشەی داهاتوو).
What a heap isهیپ چییە
A complete binary treeداری دووانیی تەواو
A tree in which every node has at most two children, called the left child and the right child.
کە تێیدا هەموو نۆدێک زۆرترین دوو منداڵی هەیە: منداڵی چەپ و منداڵی ڕاست.
A binary tree gives every node 0, 1 or 2 children. It is complete when every level is full except perhaps the last, and the last level is filled from the left with no gaps. In other words, all the nodes of one level get their children before any node of the next level does. Because of this shape a heap never has holes, and that is what lets it live in a simple list (next screen).
بە هەر 0، 1 یان 2 منداڵ دەدات. کاتێک تەواوە کە هەموو ئاستەکان پڕ بن، تەنها دوایین ئاست لەوانەیە پڕ نەبێت، بەڵام ئەویش دەبێت لە چەپەوە بەبێ بۆشایی پڕ کرابێتەوە. بە واتایەکی تر، هەموو ئاستێک منداڵەکانیان وەردەگرن پێش ئەوەی هیچ لە ئاستی داهاتوودا منداڵی هەبێت. بەهۆی ئەم شێوەیەوە هەرگیز کونی تێدا نییە و ئەمەیە ڕێگە دەدات لە سادەدا بژی (لاپەڕەی داهاتوو).
A heap stored in a listهیپ لە لیستێکدا هەڵگیراوە
A complete tree has no holes, so we can write its values level by level, left to right, into a plain list. The root is at index 0. No arrows or pointers are needed: simple arithmetic on the index finds the parent and the children. In Lab 3 every node of the drawing was labelled with its index for exactly this reason.
تەواو هیچ کونێکی تێدا نییە، بۆیە دەتوانین نرخەکانی ئاست بە ئاست، لە چەپەوە بۆ ڕاست، لە سادەدا بنووسین. لە 0دایە. هیچ تیر یان ئاماژەیەک پێویست نییە: حیسابێکی سادە لەسەر باوک و منداڵەکان دەدۆزێتەوە. لە تاقیگەی ٣دا هەموو لە وێنەکەدا بە نیشانە کرابوو، ڕێک بۆ ئەم مەبەستە.
| To find…بۆ دۆزینەوەی… | Ruleیاسا | Example (i = 1)نموونە (i = 1) |
|---|---|---|
| the parent of index iباوکی i | (i - 1) // 2 | (1 - 1) // 2 = 0 |
| the left childمنداڵی چەپ | 2 * i + 1 | 2 * 1 + 1 = 3 |
| the right childمنداڵی ڕاست | 2 * i + 2 | 2 * 1 + 2 = 4 |
The lab works the parent rule by hand: node 8 at index 5 has parent (5 − 1) / 2 = 2, the node at index 2; node 2 at index 6 gives (6 − 1) / 2 = 2.5, which becomes 2 when we keep only the whole part. Python's // (floor division) does that rounding down for us. The lab also draws arrows going back up to the parent and down to the children: those are exactly the two formulas.
تاقیگەکە یاسای باوک بە دەست حیساب دەکات: 8 لە 5 باوکەکەی (5 − 1) / 2 = 2ـە، واتە ئەو لە 2دایە؛ 2 لە 6 (6 − 1) / 2 = 2.5 دەدات، کە دەبێتە 2 کاتێک تەنها بەشە تەواوەکەی دەهێڵینەوە. //ـی (دابەشکردنی خوارەوە) ئەم بچووککردنەوەیە بۆمان دەکات. تاقیگەکە تیریش دەکێشێت کە بۆ سەرەوە دەگەڕێنەوە بۆ باوک و بۆ خوارەوە بۆ منداڵەکان: ئەمانە ڕێک دوو هاوکێشەکەن.
heap = [3, 5, 7, 6, 11, 8, 9] # a min-heap stored in a list
for i in range(len(heap)):
left, right = 2 * i + 1, 2 * i + 2
children = [heap[c] for c in (left, right) if c < len(heap)]
parent = heap[(i - 1) // 2] if i > 0 else None
print(f"index {i}: value {heap[i]:2} parent {parent} children {children}")index 0: value 3 parent None children [5, 7] index 1: value 5 parent 3 children [6, 11] index 2: value 7 parent 3 children [8, 9] index 3: value 6 parent 5 children [] index 4: value 11 parent 5 children [] index 5: value 8 parent 7 children [] index 6: value 9 parent 7 children []
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4
The two child indexes of i.
دوو منداڵەکانی i.
- Lineدێڕی 5
Keep only the child indexes that exist (inside the list).
تەنها ئەو منداڵ بهێڵەوە کە هەن (لە ناو ).
- Lineدێڕی 6
Index 0 is the root and has no parent.
0 و باوکی نییە.
Inserting: sift upزیادکردن: هەڵکشان
Restoring a heap after adding an item at the bottom: in a min-heap the item swaps places with its parent again and again while it is smaller.
ڕێکخستنەوەی دوای زیادکردنی دانەیەک لە خوارەوە: لە دانەکە تا لە باوکەکەی بچووکتر بێت جار لە دوای جار شوێنی لەگەڵ دەگۆڕێتەوە.
To insert a value, put it in the next free place, at the bottom row as far left as possible (the end of the list). The tree is still complete, but the order may be broken. Sift up (also called heapify up or bubble up) repairs it: while the new value is smaller than its parent, swap the two. Stop when the parent is smaller or equal, or when the value reaches the root. Inserting a smaller value is not an error: it is the normal case that starts the sift-up.
بۆ زیادکردنی نرخێک، لە یەکەم شوێنی بەتاڵدا دایبنێ، لە ڕیزی خوارەوە هەتا دەکرێت لە لای چەپ (کۆتایی ). هێشتا تەواوە، بەڵام لەوانەیە ڕیزبەندییەکە تێکچووبێت. (پێی دەوترێت heapify up یان bubble upش) چاکی دەکاتەوە: تا نرخە نوێیەکە لە باوکەکەی بچووکترە، جێی هەردووکیان بگۆڕە. کاتێک باوکەکە بچووکتر یان یەکسان بوو، یان نرخەکە گەیشتە ، بوەستە. زیادکردنی نرخێکی بچووکتر هەڵە نییە: دۆخی ئاساییە کە دەست پێدەکات.
A max-heap works the same way with the comparison reversed. Example: insert 7 into the max-heap 6; 5, 3; 4, 2, 1. Put 7 at the bottom, under 3. 7 > 3, swap. 7 > 6, swap. 7 is now the root: 7; 5, 6; 4, 2, 1, 3.
بە هەمان شێوە کار دەکات بەڵام بەراوردەکە پێچەوانەیە. نموونە: 7 بخە ناو 6; 5, 3; 4, 2, 1. 7 لە خوارەوە دابنێ، لە ژێر 3. 7 > 3، جێیان بگۆڕە. 7 > 6، جێیان بگۆڕە. ئێستا 7 : 7; 5, 6; 4, 2, 1, 3.
Min-heaps: parent no larger than its children, storing the tree in a list, and how sift up and sift down repair the order.
: لە خۆی گەورەتر نییە، لە هەڵدەگیرێت، هەروەها چۆن و ڕیزبەندییەکە چاک دەکەنەوە.
Watch 3:10-6:01: sift up, then sift down (next screen).
لە 3:10 تا 6:01 سەیر بکە: ، پاشان (شاشەی داهاتوو).
Removing the minimum: sift downلابردنی بچووکترین: داکشان
Restoring a heap after removing the top item: the last item is moved to the top and, in a min-heap, swaps places with its smaller child until it is in the right place.
ڕێکخستنەوەی دوای لابردنی دانەی سەرەوە: دوایین دانە دەخرێتە سەرەوە و لە لەگەڵ منداڵە بچووکترەکەی شوێن دەگۆڕێتەوە تا دەگاتە شوێنی دروستی خۆی.
Deleting from a heap always means deleting the minimum, the root (in a max-heap, the maximum). Take the root out, then move the last item (bottom row, furthest right) to the top, so the tree stays complete. Now the top value is probably too big. Sift down (heapify down) repairs it: compare it with its children and, if it is bigger than the smaller child, swap with that smaller child. Repeat until it is not bigger than its children or it has no children.
سڕینەوە لە هەمیشە واتە سڕینەوەی بچووکترین، واتە (لە گەورەترین). دەربهێنە، پاشان دوایین دانە (ڕیزی خوارەوە، دوورترین لە لای ڕاست) بگوازەوە بۆ سەرەوە، بۆ ئەوەی تەواو بمێنێتەوە. ئێستا نرخی سەرەوە لەوانەیە زۆر گەورە بێت. (heapify down) چاکی دەکاتەوە: لەگەڵ منداڵەکانی بەراوردی بکە و ئەگەر لە منداڵە بچووکەکە گەورەتر بوو، لەگەڵ ئەو منداڵە بچووکەدا جێ بگۆڕە. دووبارەی بکەرەوە تا لە منداڵەکانی گەورەتر نەبێت یان منداڵی نەبێت.
In a max-heap the rule is mirrored: swap with the larger child. Example: delete the root 10 from 10; 5, 8; 3, 4, 2, 1. Move the last item, 1, to the top. 1 is smaller than both children, so swap with the larger one, 8. 1 is still smaller than its child 2, so swap again. Result: 8; 5, 2; 3, 4, 1.
لە یاساکە پێچەوانە دەبێتەوە: لەگەڵ منداڵە گەورەکە جێ بگۆڕە. نموونە: (10) لە 10; 5, 8; 3, 4, 2, 1 بسڕەوە. دوایین دانە (1) بگوازەوە بۆ سەرەوە. 1 لە هەردوو منداڵەکەی بچووکترە، بۆیە لەگەڵ گەورەکەیان (8) جێ بگۆڕە. 1 هێشتا لە منداڵەکەی (2) بچووکترە، بۆیە دووبارە جێ بگۆڕە. ئەنجام: 8; 5, 2; 3, 4, 1.
Python's heapq moduleمۆدیوڵی heapqـی Python
You never have to write sift-up and sift-down yourself. Python's heapq module keeps a normal list in heap order for you. Its name means heap queue:
پێویست ناکات خۆت و بنووسیت. heapqـی ئاسایی بۆت بە ڕیزبەندیی دەهێڵێتەوە. ناوەکەی واتە heap queue ( ):
| Callبانگکردن | What it doesچی دەکات | Costتێچوو |
|---|---|---|
heapq.heappush(h, x) | insert x (sift up)x زیاد دەکات () | O(log n) |
heapq.heappop(h) | remove and return the smallest (sift down)بچووکترین لادەبات و دەیگەڕێنێتەوە () | O(log n) |
h[0] | look at the smallest without removing itسەیری بچووکترین دەکات بەبێ لابردنی | O(1) |
heapq.heapify(h) | turn an existing list into a heap, in place هەبوو لە شوێنی خۆیدا دەکات بە | O(n) |
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
print(heap) # the smallest is at index 0
smallest = heapq.heappop(heap) # remove and return the smallest
print(smallest)
print(heap)[1, 3, 4] 1 [3, 4]
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4-6
Push 3, 1 and 4 in any order.
3، 1 و 4 بە هەر ڕیزێک زیاد بکە.
- Lineدێڕی 7
The list is in heap order: the smallest, 1, is at index 0.
بە ڕیزبەندیی : بچووکترین، 1، لە 0دایە.
- Lineدێڕی 9
heappopalways returns the smallest.heappopهەمیشە بچووکترین دەگەڕێنێتەوە.
import heapq
numbers = [9, 4, 7, 1, 8]
heapq.heapify(numbers) # turn the list into a heap, in place
print(numbers)
print(numbers[0]) # look at the smallest without removing it[1, 4, 7, 9, 8] 1
Using Python's heapq: heapify, heappush, heappop and reading the smallest item.
بەکارهێنانی heapq لە : heapify، heappush، heappop و خوێندنەوەی بچووکترین .
Watch 13:16-18:33: heapify, heappush and heappop in Python's heapq, then a short heap sort with heapq.
لە 13:16 تا 18:33 سەیر بکە: heapify، heappush و heappop لە heapq، پاشان بە کورتی بە heapq.
Python's heapq moduleمۆدیوڵی heapqـی Python
Checking the lab drawing with Pythonپشکنینی وێنەی تاقیگەکە بە Python
Python can check our corrections. This program tests the tree from the lab drawing and our valid heap, then repeats the insert and remove from the last two screens with heapq:
دەتوانێت ڕاستکردنەوەکانمان بپشکنێت. ئەم وێنەکەی تاقیگە و ئێمە تاقی دەکاتەوە، پاشان زیادکردن و لابردنی دوو لاپەڕەی پێشوو بە heapq دووبارە دەکاتەوە:
import heapq
def is_min_heap(a):
"""True if every parent is smaller than or equal to its children."""
for i in range(1, len(a)):
parent = (i - 1) // 2
if a[i] < a[parent]:
print(f" index {i} (value {a[i]}) is smaller than its parent "
f"index {parent} (value {a[parent]})")
return False
return True
print(is_min_heap([3, 5, 7, 6, 11, 8, 2])) # the tree in the lab drawing
print(is_min_heap([3, 5, 7, 6, 11, 8, 9])) # a valid min-heap
h = [3, 5, 7, 6, 11, 8, 9]
heapq.heappush(h, 4) # insert 4: it sifts up past 6 and 5
print(h, is_min_heap(h))
print(heapq.heappop(h)) # remove the minimum: 3
print(h, is_min_heap(h))index 6 (value 2) is smaller than its parent index 2 (value 7) False True [3, 4, 7, 5, 11, 8, 9, 6] True 3 [4, 5, 7, 6, 11, 8, 9] True
The results match the two figures exactly: [3, 4, 7, 5, 11, 8, 9, 6] after the insert, and [4, 5, 7, 6, 11, 8, 9] after removing 3.
ئەنجامەکان ڕێک لەگەڵ دوو وێنەکەدا یەک دەگرنەوە: [3, 4, 7, 5, 11, 8, 9, 6] دوای زیادکردن و [4, 5, 7, 6, 11, 8, 9] دوای لابردنی 3.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4-12
Check every child against its parent
(i - 1) // 2.هەموو منداڵێک لەگەڵ باوکەکەیدا
(i - 1) // 2بەراورد بکە.- Lineدێڕی 15
The tree as drawn in Lab 3.
وەک لە تاقیگەی ٣دا کێشراوە.
- Lineدێڕی 18-20
Insert 4 into the valid heap.
4 بخە ناو .
- Lineدێڕی 22-23
Remove the minimum.
بچووکترین لاببە.
heapq makes only min-heaps in the Python version used by the labs. To get a max-heap, store each value with a minus sign: the largest value becomes the smallest. (Python 3.14 added ready-made max-heap functions such as heapq.heappush_max().)
لەو وەشانەی کە تاقیگەکان بەکاری دەهێنن، heapq تەنها دروست دەکات. بۆ وەرگرتنی ، هەر نرخێک بە نیشانەی سالبەوە هەڵبگرە: گەورەترین نرخ دەبێتە بچووکترین. ( 3.14 چەند ئامادەی بۆ زیاد کرد، وەک heapq.heappush_max().)
import heapq
# Store -value in a min-heap to get a max-heap (works in every Python 3).
max_heap = [-6, -5, -3, -4, -2, -1] # the max-heap 6; 5, 3; 4, 2, 1
heapq.heappush(max_heap, -7) # insert 7
print([-v for v in max_heap])
max_heap = [-10, -5, -8, -3, -4, -2, -1] # the max-heap 10; 5, 8; 3, 4, 2, 1
largest = -heapq.heappop(max_heap) # delete the root
print(largest, [-v for v in max_heap])[7, 5, 6, 4, 2, 1, 3] 10 [8, 5, 2, 3, 4, 1]
Both results are the same as the hand-worked max-heap examples: 7; 5, 6; 4, 2, 1, 3 and 8; 5, 2; 3, 4, 1.
هەردوو ئەنجامەکە وەک نموونە دەستکردەکانی : 7; 5, 6; 4, 2, 1, 3 و 8; 5, 2; 3, 4, 1.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4-6
The max-heap insertion example: insert 7.
نموونەی زیادکردن لە : زیادکردنی 7.
- Lineدێڕی 8-10
The max-heap deletion example: delete the root 10.
نموونەی سڕینەوە لە : سڕینەوەی (10).
Priorities with tuplesپێشینەیی بە تاپڵەکان
A search frontier holds places, not bare numbers. The trick is to push tuples whose first value is the priority. Python compares tuples value by value from the left, so the heap orders them by priority. The lab notes first tried pairs (priority, item):
گەڕان شوێن هەڵدەگرێت، نەک تەنها ژمارە. فێڵەکە ئەوەیە زیاد بکەیت کە یەکەم نرخیان پێشینەییە. نرخ بە نرخ لە چەپەوە بەراورد دەکات، بۆیە بەپێی پێشینەیی ڕیزیان دەکات. تێبینییەکانی تاقیگە سەرەتا جووتی (priority, item)یان تاقی کردەوە:
import heapq
frontier = []
heapq.heappush(frontier, (4, 'a')) # (priority, item)
heapq.heappush(frontier, (1, 'b'))
heapq.heappush(frontier, (3, 'c'))
heapq.heappush(frontier, (2, 'd'))
heapq.heappush(frontier, (6, 'e'))
while frontier:
priority, item = heapq.heappop(frontier)
print(priority, item)1 b 2 d 3 c 4 a 6 e
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 4-8
Each entry is a tuple: priority first, then the item.
هەر دانەیەک : سەرەتا پێشینەیی، پاشان دانەکە.
Pairs break when two entries have the same priority. Then Python compares the second values, the items. Two maze points cannot be compared, so the program crashes:
جووتەکان تێک دەچن کاتێک دوو دانە هەمان پێشینەیییان هەبێت. ئەو کاتە نرخە دووەمەکان، واتە دانەکان، بەراورد دەکات. دوو خاڵی ناتوانرێت بەراورد بکرێن، بۆیە تێک دەچێت:
import heapq
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
frontier = []
heapq.heappush(frontier, (5, Point(0, 1)))
heapq.heappush(frontier, (5, Point(1, 0))) # same priority 5!Traceback (most recent call last):
File "pq_tie.py", line 12, in <module>
heapq.heappush(frontier, (5, Point(1, 0))) # same priority 5!
TypeError: '<' not supported between instances of 'Point' and 'Point'TypeError: Python tried Point < Point to break the tie. (Python prints the full path of your file; it is shortened here.)
TypeError: هەوڵی دا Point < Point بکات بۆ شکاندنی یەکسانییەکە. ( ڕێڕەوی تەواوی فایلەکەت چاپ دەکات؛ لێرەدا کورت کراوەتەوە.)
The fix used in the labs is a counter in the middle: (priority, count, item). Every entry gets a different count, so a tie on priority is decided by the count, and the items themselves are never compared. Python's documentation recommends exactly this: the entry count is a tie-breaker, and equal priorities come out in the order they were added.
ئەو چارەسەرەی تاقیگەکان بەکاری دەهێنن لە ناوەڕاستدا: (priority, count, item). هەموو دانەیەک ژمارەیەکی جیاواز وەردەگرێت، بۆیە یەکسانی لە پێشینەییدا بە ژمارەکە یەکلا دەکرێتەوە و خودی دانەکان هەرگیز بەراورد ناکرێن. بەڵگەنامەی ڕێک ئەمە پێشنیار دەکات: ژمارەی دانەکە یەکلاکەرەوەی یەکسانییە و پێشینەیی یەکسان بە ڕیزی زیادکردنیان دەردەچن.
import heapq
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __repr__(self):
return f"({self.x}, {self.y})"
frontier = []
count = 0
for priority, point in [(5, Point(0, 1)), (5, Point(1, 0)), (2, Point(2, 2))]:
heapq.heappush(frontier, (priority, count, point)) # count breaks ties
count += 1
while frontier:
priority, _, point = heapq.heappop(frontier)
print(priority, point)2 (2, 2) 5 (0, 1) 5 (1, 0)
The two points with priority 5 come out in the order they were pushed.
دوو خاڵەکەی پێشینەیی 5یان هەیە بە ڕیزی زیادکردنیان دەردەچن.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 13-17
countgrows by one for every push, so no two entries share it.countبە هەر زیادکردنێک یەک زیاد دەکات، بۆیە هیچ دوو دانەیەک هەمان ژمارەیان نییە.- Lineدێڕی 20
Unpack three values;
_means “I do not need this one”.سێ نرخ دەربهێنە؛
_واتە «پێویستم بەمە نییە».
Priorities with tuplesپێشینەیی بە تاپڵەکان
Two bugs in the lab notesدوو باگ لە تێبینییەکانی تاقیگەدا
The lab's scratch file pushes the five triples, then pops them in a loop. As written, it crashes:
فایلی ڕاهێنانی تاقیگەکە پێنج زیاد دەکات، پاشان لە دەریاندەهێنێت. وەک نووسراوە، تێک دەچێت:
import heapq
frontier = []
heapq.heappush(frontier, (4, 0, 'a'))
heapq.heappush(frontier, (1, 1, 'b'))
heapq.heappush(frontier, (3, 2, 'c'))
heapq.heappush(frontier, (2, 3, 'd'))
heapq.heappush(frontier, (6, 4, 'e'))
while frontier:
_, v = heapq.heappop(frontier)
print(v)
# To get the keys:
m, v = heapq.heappop(frontier)
print(m, v)Traceback (most recent call last):
File "pq_bug.py", line 11, in <module>
_, v = heapq.heappop(frontier)
ValueError: too many values to unpack (expected 2)The program stops at bug 1 before bug 2 can show itself. (The file path is shortened here.)
لە ١دا دەوەستێت پێش ئەوەی ٢ خۆی پیشان بدات. (ڕێڕەوی فایلەکە لێرەدا کورت کراوەتەوە.)
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 11
Bug 1: each entry has 3 values, but only 2 names receive them.
١: هەر دانەیەک 3 نرخی هەیە، بەڵام تەنها 2 ناو وەریاندەگرن.
- Lineدێڕی 15
Bug 2: a second pop in the same pass skips items and would finally pop from an empty heap.
٢: دەرهێنانێکی دووەم لە هەمان خولدا دانەکان بازدەدات و لە کۆتاییدا لە بەتاڵ دەردەهێنێت.
import heapq
frontier = []
heapq.heappush(frontier, (4, 0, 'a')) # (priority, count, item)
heapq.heappush(frontier, (1, 1, 'b'))
heapq.heappush(frontier, (3, 2, 'c'))
heapq.heappush(frontier, (2, 3, 'd'))
heapq.heappush(frontier, (6, 4, 'e'))
while frontier:
m, _, v = heapq.heappop(frontier) # one pop per loop, three names
print(m, v)1 b 2 d 3 c 4 a 6 e
The items come out as b, d, c, a, e, ordered by their priorities 1, 2, 3, 4, 6, which is what the note's comment promised.
دانەکان بە ڕیزی b، d، c، a، e دەردەچن، بەپێی پێشینەییەکانیان 1، 2، 3، 4، 6، کە ئەوەیە تێبینییەکە بەڵێنی دابوو.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 11
m, _, v: the priority, the count (ignored with_) and the item.m, _, v: پێشینەیی، ژمارەکە (بە_پشتگوێ دەخرێت) و دانەکە.
Priorities with tuplesپێشینەیی بە تاپڵەکان
Coming next: Manhattan distance as the priorityلە داهاتوودا: دووریی مانهاتن وەک پێشینەیی
In Lab 3 the priority of a maze cell is its heuristic: an estimate of how far it is from the goal. The lab writes it as “pêwer”, Kurmanji for measure. The heuristic used is the Manhattan distance: how far the cell is from the goal vertically plus horizontally. Greedy best-first search explains it in full; here is the function from the lab notes:
لە تاقیگەی ٣دا پێشینەیی خانەیەکی خانەکەیە: مەزەندەیەک بۆ ئەوەی چەند لە ئامانجەوە دوورە. تاقیگەکە بە «پێوەر» (pêwer)ی کورمانجی دەینووسێت، واتە measure. ئەو بەکار دێت ـە: خانەکە چەند لە ئامانجەوە دوورە بە ستوونی لەگەڵ بە ئاسۆیی. گەڕانی چاوچنۆکانە بە تەواوی ڕوونی دەکاتەوە؛ ئەمە ناو تێبینییەکانی تاقیگەیە:
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def manhattan(current, end):
return abs(current.x - end.x) + abs(current.y - end.y)
start = Point(6, 0)
end = Point(0, 11)
print(manhattan(start, end))17
|6 − 0| + |0 − 11| = 6 + 11 = 17: the start of the Lab 3 maze is 17 steps from the goal if there were no walls.
|6 − 0| + |0 − 11| = 6 + 11 = 17: دەستپێکی تاقیگەی ٣ ئەگەر دیوار نەبوایە 17 هەنگاو لە ئامانجەوە دوور دەبوو.
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 7-8
Rows apart plus columns apart, always as positive numbers (
abs).جیاوازیی ڕیزەکان لەگەڵ جیاوازیی ستوونەکان، هەمیشە وەک (
abs).
The Lab 3 maze has 7 rows, numbered 0–6 from top to bottom, and 12 columns, numbered 0–11 from left to right. The start is (6, 0), bottom left, and the goal is (0, 11), top right.
تاقیگەی ٣ حەوت ڕیزی هەیە، لە سەرەوە بۆ خوارەوە بە 0–6 ژمارە کراون و 12 ستوون، لە چەپەوە بۆ ڕاست بە 0–11 ژمارە کراون. دەستپێک (6, 0)ـە، خوارەوەی لای چەپ و ئامانج (0, 11)ـە، سەرەوەی لای ڕاست.
Common mistakesهەڵە باوەکان
| Mistakeهەڵە | Betterباشتر |
|---|---|
| “In a min-heap the children are smaller than the parent.”«لە منداڵەکان لە باوک بچووکترن.» | Parent ≤ children; the root is the minimum.باوک ≤ منداڵەکان؛ بچووکترینە. |
| Stopping sift-up after one swap.وەستاندنی دوای یەک گۆڕین. | Keep swapping while the value is smaller than its parent.بەردەوام جێ بگۆڕە تا نرخەکە لە باوکەکەی بچووکترە. |
| Sift-down with the larger child in a min-heap. لەگەڵ منداڵە گەورەکە لە . | Always swap with the smaller child.هەمیشە لەگەڵ منداڵە بچووکەکە جێ بگۆڕە. |
Expecting print(heap) to show a sorted list.چاوەڕوانی ئەوەی print(heap) ڕیزکراو پیشان بدات. | Only heap[0] is guaranteed to be the smallest; pop repeatedly to get sorted order.تەنها heap[0] دڵنیایە کە بچووکترینە؛ بۆ ڕیزبەندیی تەواو چەند جار دەریبهێنە. |
Pushing (priority, item) when items cannot be compared.زیادکردنی (priority, item) کاتێک دانەکان بەراورد ناکرێن. | Push (priority, count, item) with a unique count.(priority, count, item) بە ژمارەیەکی بێهاوتا زیاد بکە. |
| Unpacking 2 names from a 3-value tuple, or popping twice per loop.دەرهێنانی 2 ناو لە 3 نرخی، یان دوو جار دەرهێنان لە هەر خولێکدا. | m, _, v = heapq.heappop(h), once per pass.m, _, v = heapq.heappop(h)، لە هەر خولێکدا یەک جار. |
Mixing tuples and lists in one heap ([h, count, p] and (h, count, p)).تێکەڵکردنی و لە یەک ([h, count, p] و (h, count, p)). | Use tuples everywhere; Python cannot compare a list with a tuple. (This bug is in the greedy search lab.)لە هەموو شوێنێک بەکار بهێنە؛ ناتوانێت لەگەڵ بەراورد بکات. (ئەم لە کۆدی تاقیگەی گەڕانی چاوچنۆکانەدایە.) |
Exercisesڕاهێنانەکان
Without running code, decide whether each list is a min-heap: (a) [2, 5, 3, 9, 6, 4], (b) [1, 4, 2, 3]. Then check with a short function.
بەبێ کارپێکردنی کۆد، بڕیار بدە ئایا هەر : (أ) [2, 5, 3, 9, 6, 4]، (ب) [1, 4, 2, 3]. پاشان بە کورت بیپشکنە.
Show answerوەڵامەکە پیشان بدە
(a) Yes: 2 ≤ 5 and 3; 5 ≤ 9 and 6; 3 ≤ 4. (b) No: index 3 holds 3, and its parent at index 1 holds 4, which is bigger.
(أ) بەڵێ: 2 ≤ 5 و 3؛ 5 ≤ 9 و 6؛ 3 ≤ 4. (ب) نەخێر: 3 نرخی 3ی تێدایە و باوکەکەی لە 1 نرخی 4ی تێدایە، کە گەورەترە.
def is_min_heap(a):
for i in range(1, len(a)):
if a[i] < a[(i - 1) // 2]: # a child smaller than its parent
return False
return True
print(is_min_heap([2, 5, 3, 9, 6, 4]))
print(is_min_heap([1, 4, 2, 3]))True False
Insert 1 into the heap [3, 4, 7, 5, 11, 8, 9, 6]. Write the list after every swap, then check your final list with heapq.heappush.
1 بخە ناو [3, 4, 7, 5, 11, 8, 9, 6]. دوای هەر گۆڕینێک بنووسە، پاشان بە heapq.heappush بپشکنە.
Hintئاماژە
The new value starts at index 8; its parent is (8 − 1) // 2 = 3.
نرخە نوێیەکە لە 8 دەست پێدەکات؛ باوکەکەی (8 − 1) // 2 = 3ـە.
Show answerوەڵامەکە پیشان بدە
1 goes to index 8 (parent index 3, value 5): swap → [3, 4, 7, 1, 11, 8, 9, 6, 5]. Parent index 1 (value 4): swap → [3, 1, 7, 4, 11, 8, 9, 6, 5]. Parent index 0 (value 3): swap → [1, 3, 7, 4, 11, 8, 9, 6, 5]. It is the root: stop.
1 دەچێتە 8 ( باوک 3، نرخ 5): گۆڕین ← [3, 4, 7, 1, 11, 8, 9, 6, 5]. باوک 1 (نرخ 4): گۆڕین ← [3, 1, 7, 4, 11, 8, 9, 6, 5]. باوک 0 (نرخ 3): گۆڕین ← [1, 3, 7, 4, 11, 8, 9, 6, 5]. گەیشتە : بوەستە.
import heapq
h = [3, 4, 7, 5, 11, 8, 9, 6]
heapq.heappush(h, 1)
print(h)[1, 3, 7, 4, 11, 8, 9, 6, 5]
In a heap stored in a list, which indexes hold the children of index 4, and which index holds the parent of index 10?
لە کە لە هەڵگیراوە، کام منداڵەکانی 4 هەڵدەگرن و کام باوکی 10 هەڵدەگرێت؟
Show answerوەڵامەکە پیشان بدە
Children of 4: 2·4 + 1 = 9 and 2·4 + 2 = 10. Parent of 10: (10 − 1) // 2 = 4. The two rules agree, as they must.
منداڵەکانی 4: 2·4 + 1 = 9 و 2·4 + 2 = 10. باوکی 10: (10 − 1) // 2 = 4. دوو یاساکە یەک دەگرنەوە، وەک پێویستە.
Use heapq to print these tasks from most to least urgent (1 = most urgent). Equal priorities must keep the order in which they were added: wash dishes (2), homework (1), call Hana (2), buy bread (3).
heapq بەکار بهێنە بۆ چاپکردنی ئەم کارانە لە بەپەلەترینەوە بۆ کەمترین (1 = بەپەلەترین). پێشینەیی یەکسان دەبێت ڕیزی زیادکردنیان بپارێزن: شوشتنی قاپ (2)، ئەرکی ماڵەوە (1)، تەلەفۆن بۆ هانا (2)، کڕینی نان (3).
Show answerوەڵامەکە پیشان بدە
import heapq
tasks = []
count = 0
for name, priority in [("wash dishes", 2), ("homework", 1),
("call Hana", 2), ("buy bread", 3)]:
heapq.heappush(tasks, (priority, count, name))
count += 1
while tasks:
priority, _, name = heapq.heappop(tasks)
print(priority, name)1 homework 2 wash dishes 2 call Hana 3 buy bread
Explain the codeڕوونکردنەوەی کۆدەکە
- Lineدێڕی 7
The count keeps equal priorities in arrival order.
ژمارەکە پێشینەیی یەکسان بە ڕیزی هاتنیان دەهێڵێتەوە.
Print the three largest numbers of [5, 1, 9, 3, 7], largest first, using a min-heap of negative numbers. Then find a one-line heapq function that does the same.
سێ گەورەترین ژمارەی [5, 1, 9, 3, 7] چاپ بکە، گەورەترین یەکەم، بە بەکارهێنانی لە . پاشان یەک دێڕیی heapq بدۆزەوە کە هەمان کار دەکات.
Show answerوەڵامەکە پیشان بدە
import heapq
numbers = [5, 1, 9, 3, 7]
max_heap = []
for n in numbers:
heapq.heappush(max_heap, -n) # store -n: the largest becomes the smallest
for _ in range(3):
print(-heapq.heappop(max_heap)) # turn it back into a positive number
print(heapq.nlargest(3, numbers)) # heapq can also do it in one call9 7 5 [9, 7, 5]
Summary and reviewپوختە و پێداچوونەوە
- A priority queue always gives back the item with the best (smallest) priority; greedy best-first search and A* need one.
- A min-heap is a complete binary tree where every parent ≤ its children, so the minimum is at the root (a max-heap is the mirror image).
- Stored in a list: parent (i − 1) // 2, children 2i + 1 and 2i + 2.
- Insert = add at the end + sift up; remove the minimum = last item to the top + sift down with the smaller child. Both cost O(log n).
- Python's
heapq:heappush,heappop,heapify,h[0]; negate values for a max-heap. - Push
(priority, count, item)so that ties never compare the items.
- هەمیشە ئەو دانەیە دەداتەوە کە باشترین (بچووکترین) پێشینەیی هەیە؛ و A* پێویستیان پێیەتی.
- کە تێیدا هەموو باوکێک ≤ منداڵەکانیەتی، بۆیە بچووکترین لە ( وێنەی پێچەوانەیەتی).
- لە هەڵدەگیرێت: باوک (i − 1) // 2، منداڵەکان 2i + 1 و 2i + 2.
- زیادکردن = دانان لە کۆتاییدا + ؛ لابردنی بچووکترین = دوایین دانە بۆ سەرەوە + لەگەڵ منداڵە بچووکەکە. هەردووکیان O(log n) تێدەچن.
heapqـی :heappush،heappop،heapify،h[0]؛ بۆ نرخەکان سالب بکە.(priority, count, item)زیاد بکە بۆ ئەوەی یەکسانییەکان هەرگیز دانەکان بەراورد نەکەن.
What is the difference between a min-heap and a max-heap?جیاوازیی نێوان هیپی کەمینە و هیپی زۆرینە چییە؟
In a min-heap every parent ≤ its children and the root is the smallest; in a max-heap every parent ≥ its children and the root is the largest.
لە هەموو باوکێک ≤ منداڵەکانیەتی و بچووکترینە؛ لە هەموو باوکێک ≥ منداڵەکانیەتی و گەورەترینە.
Why can a heap be stored in a plain list?بۆچی هیپ دەتوانێت لە لیستێکی سادەدا هەڵبگیرێت؟
Because it is a complete binary tree: no holes, so level-by-level order fits a list and index arithmetic finds parents and children.
چونکە : هیچ کونێکی نییە، بۆیە ڕیزبەندیی ئاست بە ئاست لە جێی دەبێتەوە و حیسابی باوک و منداڵەکان دەدۆزێتەوە.
When does sift-up stop?هەڵکشان کەی دەوەستێت؟
When the value is not smaller than its parent, or when it reaches the root.
کاتێک نرخەکە لە باوکەکەی بچووکتر نییە، یان کاتێک دەگاتە .
Why does sift-down swap with the smaller child in a min-heap?بۆچی داکشان لە هیپی کەمینەدا لەگەڵ منداڵە بچووکەکە جێ دەگۆڕێت؟
The smaller child becomes the parent of the other child, so it must be the smaller of the two to keep parent ≤ children.
منداڵە بچووکەکە دەبێتە باوکی منداڵەکەی تر، بۆیە دەبێت بچووکترینی هەردووکیان بێت بۆ ئەوەی باوک ≤ منداڵەکان بمێنێتەوە.
What goes wrong with (priority, item) entries, and how is it fixed?چی هەڵە دەچێت لە دانەکانی (priority, item) و چۆن چاک دەکرێت؟
When two priorities are equal Python compares the items, which may be impossible (TypeError). A unique count in the middle, (priority, count, item), fixes it.
کاتێک دوو پێشینەیی یەکسانن دانەکان بەراورد دەکات، کە لەوانەیە نەکرێت (TypeError). ژمارەیەکی بێهاوتا لە ناوەڕاستدا، (priority, count, item)، چاکی دەکاتەوە.
Lesson complete!وانەکە تەواو بوو!
Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.
Key termsزاراوە سەرەکییەکان
Search Problems: States, Actions, Goals and Costsکێشەکانی گەڕان: دۆخەکان، کردەوەکان، ئامانج و کۆست
Related lecturesوانە پەیوەندیدارەکان
- Agent Programs, Pseudocode and Algorithm Analysisبەرنامەکانی ئەیجێنت، نیمچەکۆد و شیکارکردنی ئەلگۆریزم
- Heuristics and Greedy Best-First Searchپێوەرەکان و گەڕانی چاوچنۆکانە
- A* Searchگەڕانی A*
- Depth-Limited, Uniform-Cost, Iterative Deepening and Bidirectional Searchگەڕانی قووڵایی سنووردار، گەڕانی کەمترین کۆست، گەڕانی قووڵکردنەوەی پلەبەپلە و گەڕانی دووئاڕاستە
References and further readingسەرچاوەکان و خوێندنەوەی زیاتر
- Python documentation: heapq — Heap queue algorithm (heap invariant, priority queue implementation notes, max-heap functions)
- Python tutorial: Data structures (comparing sequences)
- Russell & Norvig, Artificial Intelligence: A Modern Approach, 4th ed. — contents (best-first search uses a priority queue; Appendix A on O() notation)
- Sedgewick & Wayne, Algorithms 4th ed. (Princeton): 2.4 Priority Queues (binary heaps, about lg n compares per insert or remove)
This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.