Priority Queues (Binary Heap)

1. Introduction
2. Array Representation of Binary Heap
3. MinHeap vs. MaxHeap
4. Insert
5. DeleteMax
6. Preserving the Heap Order Property
7. BuildHeap
8. HeapSort
9. Analysis

7. BuildHeap

Building a heap in linear time (bottom-up heap construction, build heap)

A heap can be built in linear time from an arbitrarily sorted array. This can be done by swapping items, ending up with an algorithm requiring at most kn+c swaps, where n is the number of items in the array and k and c are small constants.

This algorithm starts by examining the two lowest levels of the tree and organize all subtrees on those levels as binary heaps. Next, the algorithm moves one level up and heapifies those subtrees. This continues all the way to the root of the tree.

Let us consider a MinHeap

For every subtree, the priority of the root node is compared with the smaller child (the smaller of the child nodes has to be determined). If the priority of the child is less then that of the root, the items are swapped. In some cases, it is possible that the node swapped downward is still greater than the smaller child. This requires another swap in the smaller heap (subtree). This is repeated for the smaller heap as before, and the node can even be swapped all the way to the leaf. When all the levels up to the root of the whole tree have been processed, the structure is organized as a heap.

The following shows building a maximum heap

In case of a minimum heap, line 2 would call MIN-HEAPIFY(A, i) algorithm that works similarly to the MAX-HEAPIFY.

A heap with n = heap-size[A]is built from array A[0..n-1].

The function Max-Heapify is called repeatedly. Max-Heapify algorithm is called only for items A[⌊n/2⌋-1], A[⌊n/2⌋-2], ..., A[0], because

• rest of the items are leaf nodes and
• each of them is a heap of size 1 (the heap property cannot be violated for such a heap).

It can be shown that the time-complexity of the BUILD-MAX-HEAP algorithms is O(n).

Exercise: BuildHeap

Exercise A heap can be built from a table of random keys by using a linear time bottom-up algorithm (a.k.a., Build-Heap, Fixheap, and Bottom-Up Heap Construction). This algorithm ensures that the heap-order property (the key at each node is lower than or equal to the keys at its children) is not violated in any node. Heap order property is "father greater than its children". Instructions In this exercise, the heap is visualized both as a binary tree and vector. Both visualizations illustrate the same data structure and the exercise can be completed by swapping keys in either visualization. The swapping is done by drag & dropping a key into another node. Build-Heap Algorithm 4 Build-Max-Heap(A) for i ← heap-size[A]/2-1 downto 0 do Max-Heapify (A, i) end for Algorithm 2 Max-Heapify(A, i) l ← Left-child-index(i) r ← Right-child-index(i) if l < heap-size[A] and A[l] > A[i] then greatest ← l else greatest ← i end if if r < heap-size[A] and A[r] > A[greatest] then greatest ← r end if if greatest ≠ i then Swap(A[i],A[greatest]) Max-Heapify(A, greatest) end if