Content deleted Content added
m mark some code; though there are also big slabs of it |
|||
Line 101:
=== Insert then extract ===
Inserting an element then extracting from the heap can be done more efficiently than simply calling the insert and extract functions defined above, which would involve both an <code>upheap</code> and <code>downheap</code> operation. Instead, we can do just a <code>downheap</code> operation, as follows:
# Compare whether the item we're pushing or the peeked top of the heap is greater (assuming a max heap)
Line 220:
This implementation is used in the [[heapsort]] algorithm which reuses the space allocated to the input array to store the heap (i.e. the algorithm is done [[In-place algorithm|in-place]]). This implementation is also useful as a [[Priority queue]]. When a [[dynamic array]] is used, insertion of an unbounded number of items is possible.
The <code>upheap</code> or <code>downheap</code> operations can then be stated in terms of an array as follows: suppose that the heap property holds for the indices ''b'', ''b''+1, ..., ''e''. The sift-down function extends the heap property to ''b''−1, ''b'', ''b''+1, ..., ''e''.
Only index ''i'' = ''b''−1 can violate the heap property.
Let ''j'' be the index of the largest child of ''a''[''i''] (for a max-heap, or the smallest child for a min-heap) within the range ''b'', ..., ''e''.
| |||