Tuesday, 2 July 2013

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 2i 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(n2) 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)/2i heaps, each storing 2i-1 keys, by joining pairs of heaps storing (2i-1-1) keys. Swaps may occur.

Bottom-Up Heap Construction

Algorithm bottomUpHeap(S)
Input: a sequence S storing 2h-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 S1 and S2, each of size (n-1)/2
H1¬ bottomUpHeap(S1)
H2¬ bottomUpHeap(S2)
Create binary tree H such with k at root, H1 at left subtree
and H2 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 = ne + ni
The number of edges is e = ne + ni –1

But since in a heap, n equals the number of key-element pairs, i.e.,
n = ni   and   ne = ni + 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).