Heap Detailed Note

Heaps

• A heap is a binary tree H that stores a collection of keys at its internal nodes and satisfies two additional properties:

1. Heap-Order Property
2. Complete Binary Tree Property

• Heap-Order Property (relational): In a heap H, for every node v except the root, the key stored in v is greater than or equal to the key stored in v’s parent.

• Complete Binary Tree Property (structural): A binary tree H is complete if each level but the last is full and, in level h-1, all of the internal nodes are to the left of the external nodes.
• In a complete binary tree of height h, levels i=0,1,…,h-1 will each have 2ⁱ nodes, the maximum possible number of nodes for those levels.

---

Heaps (cont.)

• An example

---

Height of a Heap

• Proposition: A heap H storing n keys has height

.

• Justification: Due to H being complete, we know:
• The number of internal nodes n is at least

• The number of internal nodes n is at most

• Therefore,

• or

• which in turn implies:

---

Height of a Heap (cont.)

• Let’s look at that graphically:

• Consider this heap, which has height h = 4 and n = 13.

• Suppose that two more nodes are added. To maintain completeness of the tree, the two external nodes in level 4 will become internal nodes, i.e., n = 15, h = 4 = log(15 + 1).

• Add one more node: now .

---

Implementation of a Heap

 
public class HeapSimplePriorityQueue implements SimplePriorityQueue {
    BinaryTree T;
    Position last;
    Comparator comparator;
    …
}

---

Implementation of a Heap (cont.)

• Two ways to find the insertion position z in a heap:

• Special case where w is the right-most node in its level.

• General case

---

Finding the Insertion Position

Algorithm findInsertionPosition(w)
Input: Last position w
Output: Insertion position z

if root is external
    z ¬root
else
    u ¬last = w
    while (u is neither root nor a left child)
        u ¬ parent of u
    if u is a left child
        u ¬ sibling of u
   while u is not external
        u ¬ left child of u
    z ¬u
return z

---

Up-Heap Bubble

Algorithm upHeapBubble(z)
    z.setElement(key-element pair to be inserted)
    done¬ false
    while not done
        if z = root
            done ¬ true
        else
            u ¬ parent of z
        if key(z) < key(u)
            swap key-element pairs between u and z
        else
            done ¬ true
        z ¬ u

 

---

Insertion into a Heap

 

 

 

---

Insertion into a Heap (2)

 

 

---

Insertion into a Heap (3)

 

 

---

Insertion into a Heap (4)

 

---

Down-Heap Bubbling

Algorithm downHeapBubble

r ¬ root
done ¬ false
while not done
    if both children of r are external
        done¬ true
    else if right child of r is external
        s ¬ left child of r
    else
        s ¬ child of r with minimum key
    if key(s) < key(r)
        swap key-element pairs between r and s
        r¬s
    else
        done¬ true

---

Reverse Algorithm of findInsertionPosition

  Algorithm findLastPosition(w)
Input w: old last position, about to become insertion position
Output last: new last position
removeAboveExternal(right child of w)
if w = root
    return w
while w is neither root nor a right child
    w ¬ parent of w
if w is a right child
    w ¬ sibling of w
while right child of w is not external
    w ¬ right child of w
return w  

---

Removal from a Heap

 

 

---

Removal from a Heap (2)

 

---

Removal from a Heap (3)

---

Removal from a Heap (4)

---

Summary of Costs, Heap-Based Priority Queue

 

Method	Unsorted Sequence	Sorted Sequence	Heap
size, isEmpty	O(1)	O(1)	O(1)
minElement, minKey	Q(n)	O(1)	O(1)
insertItem	O(1)	O(n)	O(log n)
removeMinElement	Q(n)	O(1)	O(log n)

Height of heap = h = O(log n)

upHeapBubble Î O(h) = O(log n)

downHeapBubble ÎO(h) = O(log n)

findInsertionPosition ÎO(2h) = O(2log n) = O(logn)

findLastPosition ÎO(2h) = O(2log n) = O(log n)

---

Heap Sort

• All heap methods run in logarithmic time or better.

• If we implement PriorityQueueSort using a heap for out priority queue, insertItem and removeMinElement each take O(log k) where k is the number of elements in the heap at a given time.

• We always have n or fewer elements in the heap, so the worst-case time complexity of these methods is O(log n).

• Thus each phase takes O(n log n) time, so the overall algorithm runs in
O(n log n) + O(n log n) = O(n log n) time.
• This algorithm is known as heap-sort.

• The O(n log n) run-time performance of heap-sort is much better than the O(n²) run-time performance of selection sort and insertion sort.

---

Bottom-Up Heap Construction
• If all the keys to be stored are given in advance we can build a heap bottom-up in O(n) time.
• Note: For simplicity we shall describe bottom-up heap construction for the case
where h is the height and n is the number of keys.
• Steps:
1. Construct (n+1)/2 elementary heaps composed of one key each.
2. Construct (n+1)/4 heaps, each with 3 keys, by joining pairs of elementary heads and adding a new key as the root. The new key may be swapped with a child in order to preserve heap-order property.
3. Construct (n+1)/8 heaps, each with 7 keys, by joining pairs of 3-key heaps and adding a new key. Again swaps may occur.
….
• In the ith step, 2£i£ h, we form (n+1)/2ⁱ heaps, each storing 2ⁱ-1 keys, by joining pairs of heaps storing (2ⁱ-1-1) keys. Swaps may occur.

---

Bottom-Up Heap Construction

Algorithm bottomUpHeap(S)
Input: a sequence S storing 2^h-1 keys
Output: a heap H storing the keys in Sif S is empty then
    return an empty heap
remove the first key, k, from S
Split S into subsequences S₁ and S₂, each of size (n-1)/2
H₁¬ bottomUpHeap(S₁)
H₂¬ bottomUpHeap(S₂)
Create binary tree H such with k at root, H₁ at left subtree
                        and H₂ at    right subtree
Perform down-heap bubbling from root if necessary
return H

NOTE:  The splitting of sequences is merely a conceptual construct to help explain the recursion.  In practice, the elements of the sequence are simply inserted in order.

---

Bottom-Up Heap Construction Example

Original sequence in the example (n=15)

14,9,25,16,15,5,4,12,8,11,6,7,27,23,20

Remove first key

14,{9,25,16,15,5,4,12,8,11,6,7,27,23,20}

Enter next level in recursion (n=7)

14,{9,[25,16,15,5,4,12],8,[11,6,7,27,23,20]}

Enter next level in recursion (n=3)

14,{9,[25,(16,15),5,(4,12)],8,[11,(6,7),27,(23,20)]}

Trivial binary trees, n=1

16 15 4 12 6 7 23 20

---

Bottom-Up Heap Construction

---

Bottom-Up Heap Construction (cont.)

 

---

Bottom-Up Heap Construction (cont.)

---

Bottom-Up Heap Construction (cont.)

---

Analysis of Bottom-Up Heap Construction

• Proposition: Bottom-up heap construction with n keys takes O(n) time.
• At level h-1 (height 1), we perform (n+1)/2 insertions, each of worst-case cost O(1).
• At level h-2 (height 2), we perform (n+1)/4 insertions, each of worst-case cost O(2), i.e., O(1) for insertion, O(1) for down-heap bubbling one level,
• ::::
• At height h we perform 1 where at most h-1 levels are involved in the down-heap bubbling.

The cost of insertion at height h is O(h) in the worst-case because the cost is dominated by the swapping operations in down-heap bubbling.

One worst-case realization is when each node when inserted performs down-heap bubbling from its inorder successor node. (Right, then repeat left until an external node is reached).
 

---

Analysis of Bottom-Up Heap Construction (cont).

Every edge in the tree is used at most once for an inorder successor down-heap bubble. This assures that the number of swaps is bounded above by the number of edges.

Recall that for a tree, n represents the total number of nodes, i.e. n = n_e + n_i

The number of edges is e = n_e + n_i –1
 

But since in a heap, n equals the number of key-element pairs, i.e.,

n = n_i   and   n_e = n_i + 1,

we therefore have

e = 2n,

and the complexity of bottom-up heap construction is thus

O(e) = O(2n) = O(n).

---

Analysis of Bottom-Up Heap Construction (cont.)

---

Sequence-based Implementation of a Binary Tree
 

---

Sequence-based Implementation of a Binary Tree (cont.)

Best case

Worst case

Summary

Implications for heaps:

1. Heap-order property implies that a sequence-based heap is relatively efficient space-wise (N=O(n)).
2. The algorithms findInsertionPosition and findLastPosition are O(1).