Heap shift down
This section will introduce how to take an element out of a max heap, called shift down. Only the element with the highest priority can be taken out, which is the root node. After taking out the original 62, the following explains how to fill this max heap.
The first step is to place the last element of the array at the root node. At this point, it does not satisfy the definition of a max heap.
The adjustment process is to move this root node 16 down step by step. Since 16 is smaller than both child nodes, first compare the child nodes 52 and 30 to see which is larger, and swap positions with the larger one.
Continue comparing 16's child nodes 28 and 41. Since 41 is larger, 16 and 41 swap positions.
Continue comparing 16 with its child node 15. Since 16 is larger, no swap is needed now. Finally, our shift down operation is complete, maintaining the property of a max heap.
4. Java Example Code
Source Package Download:Download
Code of file src/example/heap/HeapShiftDown.java:
/**
* Extract an element from the max heap
*/
public class HeapShiftDown<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// Constructor, constructs an empty heap that can hold capacity elements
public HeapShiftDown(int capacity){
// The +1 here refers to the number of elements that can originally be stored; after removing the 0th position, it can only hold capacity elements
data = (T[])new Comparable[capacity+1];
count = 0;
this.capacity = capacity;
}
// Return the number of elements in the heap
public int size(){
return count;
}
// Return a boolean indicating whether the heap is empty
public boolean isEmpty(){
return count == 0;
}
// Insert a new element item into the max heap
public void insert(T item){
assert count + 1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
}
// Extract the top element from the max heap, i.e., the largest data stored in the heap
public T extractMax(){
assert count > 0;
T ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
}
// Get the top element of the max heap
public T getMax(){
assert( count > 0 );
return data[1];
}
// Swap the two elements at indices i and j in the heap
private void swap(int i, int j){
T t = data[i];
data[i] = data[j];
data[j] = t;
}
//********************
//* Max heap core helper functions
//********************
private void shiftUp(int k){
while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
swap(k, k/2);
k /= 2;
}
}
// shiftDown operation
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // In this loop iteration, data[k] and data[j] swap positions
if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
j ++;
// data[j] is the maximum of data[2*k] and data[2*k+1]
if( data[k].compareTo(data[j]) >= 0 ) break;
swap(k, j);
k = j;
}
System.out.println("shiftDown ended");
}
// Test HeapShiftDown
public static void main(String[] args) {
HeapShiftDown<Integer> heapShiftDown = new HeapShiftDown<Integer>(100);
// Number of elements in the heap
int N = 100;
// Heap element value range [0, M)
int M = 100;
for( int i = 0 ; i < N ; i ++ )
heapShiftDown.insert( new Integer((int)(Math.random() * M)) );
Integer[] arr = new Integer[N];
// Gradually extract data from the max heap using extractMax
// The extraction order should be from largest to smallest
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapShiftDown.extractMax();
System.out.print(arr[i] + " ");
}
// Ensure the arr array is sorted from largest to smallest
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}
}