Heap
What is a heap
- A heap is a binary tree storing keys at its internal nodes and satisfying the following properties:
- Heap-Order: for every internal node v other than the root, key(v) ≥ key(parent(v))
- Complete Binary Tree: let h be the height of the heap
- for i = 0, … , h − 1, there are 2^i nodes of depth i
- at depth h − 1, the internal nodes are to the left of the external nodes
- The last node of a heap is the rightmost internal node of depth h − 1
Height of a Heap
- Theorem: A heap storing n keys has height O(log n)
Proof: (we apply the complete binary tree property)- Let h be the height of a heap storing n keys
- Since there are 2i keys at depth i = 0, … , h − 2 and at least one key at depth h − 1, we have n ≥ 1 + 2 + 4 + … + 2h−2 + 1
- Thus, n ≥ 2h−1 , i.e., h ≤ log n + 1
Heaps and Priority Queues
- We can use a heap to implement a priority queue
- We store a (key, element) item at each internal node
- We keep track of the position of the last node
- For simplicity, we show only the keys in the pictures
Insertion into a Heap
- Method insertItem of the priority queue ADT corresponds to the insertion of a key k to the heap
- The insertion algorithm consists of three steps:
- Find the insertion node z (the new last node)
- Store k at z and expand z into an internal node
- Restore the heap-order property (upheap)
Upheap
- After the insertion of a new key k, the heap-order property may be violated
- Algorithm upheap restores the heap-order property by swapping k along an upward path from the insertion node
- Upheap terminates when the key k reaches the root or a node whose parent has a key smaller than or equal to k
- Since a heap has height O(log n), upheap runs in O(log n) time
Removal from a Heap
- Method removeMin of the priority queue ADT corresponds to the removal of the root key from the heap
- The removal algorithm onsists of three steps
- Replace the root key with the key of the last node w
- Compress w and its children into a leaf
- Restore the heap-order property (downheap)
Downheap
- After replacing the root key with the key k of the last node, the heap-order property may be violated
- Algorithm downheap restores the heap-order property by swapping key k along a downward path from the root
- Upheap terminates when key k reaches a leaf or a node whose children have keys greater than or equal to k
- Since a heap has height O(log n), downheap runs in O(log n) time
Updating the Last Node
- The insertion node can be found by traversing a path of O(log n) nodes
- While the current node is a right child, go to the parent node
- If the current node is a left child, go to the right child
- While the current node is internal, go to the left child
- Similar algorithm for updating the last node after a removal
Heap-Sort
- Consider a priority queue with n items implemented by means of a heap
- the space used is O(n)
- methods insertItem and removeMin take O(log n) time
- methods size, isEmpty, minKey, and minElement take time O(1) time
- Using a heap-based priority queue, we can sort a sequence of n elements in O(n log n) time
- The resulting algorithm is called heap-sort
- Heap-sort is much faster than quadratic sorting algorithms, such as insertion-sort and selection-sort
Vector-basedHeap Implementation
TODO
Merging Two Heaps
- We are given two two heaps and a key k
- We create a new heap with the root node storing k and with the two heaps as subtrees
- We perform downheap to restore the heaporder property
Bottom-up Heap Construction
- We can construct a heap storing n given keys in using a bottom-up construction with log n phases
- In phase i, pairs of heaps with 2i −1 keys are merged into heaps with 2i+1−1 keys
Analysis
- We visualize the worst-case time of a downheap with a proxy path that goes first right and then repeatedly goes left until the bottom of the heap (this path may differ from the actual downheap path)
- Since each node is traversed by at most two proxy paths, the total number of nodes of the proxy paths is O(n)
- Thus, bottom-up heap construction runs in O(n) time
- Bottom-up heap construction is faster than n successive insertions and speeds up the first phase of heap-sort
Code
package examples;
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;
import java.util.ArrayList;
import java.util.Random;
/**
* @author ps
* Various sort programs for int arrays
*/
public class SortTest {
public static long cnt;
static Random rand = new Random();
static int [] b;
/**
* swap the array elements a[i] and a[k]
* @param a int array
* @param i position in the array 'a'
* @param k position in the array 'a'
*/
static void swap(int [] a, int i, int k){
int tmp=a[i];
a[i]=a[k];
a[k]=tmp;
cnt++;
}
static void heapSort(int [] a){
// make 'a' to be an max-heap:
// for (int i=1; i<a.length; i++) upHeap(a,i);
for (int i=a.length/2;i>=0;i--) downHeap(a,i,a.length);
// System.out.println("max-heap? "+heapCheck(a));
for (int i = a.length-1; i>0; i--){
swap(a,0,i); // now a[i] is at its final position
downHeap(a, 0, i);
}
}
private static void upHeap(int[] a, int i) {
// assume a[0..i-1] is a max-heap, swap element
// at position i with its parent and so on
// until a[0..i] is a max-heap
int parent = (i-1)/2;
while (i>0 && a[parent] < a[i]){
swap(a,parent,i);
i = parent;
parent = (i-1)/2;
}
}
private static void downHeap(int[] a, int i, int len) {
// assume a [i..len-1] is a max-heap, but the element
// at position i possibly violates the heap condition.
// swap a[i] with its bigger child until a[i..len-1] is a heap.
int left = i*2+1;
while (left < len){
int cand = left;
int right = left+1;
// find the bigger child (if there are two)
if (right < len && a[right] > a[left]) cand = right;
if (a[i] >= a[cand]) break;
swap(a,i,cand);
i = cand;
left = i*2+1;
}
}
private static boolean heapCheck(int [] a){
for (int i=1;i<a.length;i++) if (a[(i-1)/2]<a[i]) return false;
return true; // we have a correct max-heap
}
public static void main(String[] args) {
long t1=0,t2=0,te1=0,te2=0,eTime=0,time=0;
int n = 50000000;
// we need a random generator
Random rand=new Random(Integer.MAX_VALUE);
//rand.setSeed(54326346); // initialize always in the same state
ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();
// new array
int [] a = new int[n];
// fill it randomly
for (int i=0;i<a.length ;i++) {
a[i]=rand.nextInt(n);
}
for (int i=0;i<a.length ;i++) {
swap(a,i,rand.nextInt(n-1));
}
cnt=0; // for statistcs reasons
// get Time
te1=System.nanoTime();
t1 = threadBean.getCurrentThreadCpuTime();
heapSort(a);
// System.out.println("heap? "+heapCheck(a));
te2 = System.nanoTime();
t2 = threadBean.getCurrentThreadCpuTime();
time=t2-t1;
eTime=te2-te1;
System.out.println("# elements: "+n);
System.out.println("CPU-Time usage: "+time/1000000.0+" ms");
System.out.println("elapsed time: "+eTime/1e6+" ms");
System.out.println("sorted? "+heapCheck(a));
System.out.println("swap operation needed: "+cnt);
}
}