Page 216 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 10: Heaps

that is at least as large as its parent; in a max-heap, each item has a priority that is no larger than Notes
its parent.
The minimum priority item in a min-heap (or the maximum priority item in a max-heap) may
always be found at position 0 of the array. To remove this item from the priority queue, the last
item x in the array is moved into its place, and the length of the array is decreased by one. Then,
while item x and its children do not satisfy the heap property, item x is swapped with one of its
children (the one with the smallest priority in a min-heap, or the one with the largest priority in
a max-heap), moving it downward in the tree and later in the array, until eventually the heap

property is satisfied. The same downward swapping procedure may be used to increase the
priority of an item in a min-heap, or to decrease the priority of an item in a max-heap.
To insert a new item into the heap, the item is appended to the end of the array, and then while
the heap property is violated it is swapped with its parent, moving it upward in the tree and

earlier in the array, until eventually the heap property is satisfied. The same upward-swapping
procedure may be used to decrease the priority of an item in a min-heap, or to increase the
priority of an item in a max-heap.
To create a new heap from an array of n items, one may loop over the items in reverse order,
starting from the item at position n − 1 and ending at the item at position 0, applying the
downward-swapping procedure for each item.

To implement Prim’s algorithm efficiently, we need a data structure that will store the vertices of
S in a way that allows the vertex joined by the minimum cost edge to be selected quickly.
A heap is a data structure consisting of a collection of items, each having a key. The basic
operations on a heap are:
1. insert(i,k,h). Add item i to heap h using k as the key value.
2. deletemin(h). Delete and return an item of minimum key from h.
3. changekey(i,k,h). Change the key of item i in heap h to k.
4. key(i,h). Return the key value for item i.

The heap is among the most widely applicable non-elementary data structure.

Heaps can be implemented efficiently, using a heap-ordered tree.
1. each tree node contains one item and each item has a real-valued key
2. the key of each node is at least as large the key of its parent (excepting the root)

For integer d >1, a d-heap is a heap-ordered d-ary tree that is “heapshaped.”
1. let T be an infinite d-ary tree, with vertices numbered in breadth-fi rst order

2. a subtree of T is heap-shaped if its vertices have consecutive numbers 1, 2, ..., n

4 4
item number
key
8 4 2 7 9 10

10 1 11 7 5 6 3
5 6 8 15 11 12 13

The depth of a d-heap with n nodes is ≤ [log n].
d

LOVELY PROFESSIONAL UNIVERSITY 211