YouTipHeap Shift Down
This section will introduce how to extract an element from a max heap, called shift down. Only the element with the highest priority can be extracted, which is the root node. After extracting the original 62, we will introduce how to fill the vacancy in this max heap.
!(#)
In the first step, we 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 moves the root node 16 down step by step. 16 is smaller than all its child nodes. First, we compare the child nodes 52 and 30 to see which is larger, and swap with the larger one.
!(#)
Continue comparing the child nodes 28 and 41 of 16. Since 41 is larger, we swap 16 and 41.
!(#)
Continue comparing 16 with the child node 15. Since 16 is larger, no swap is needed. Finally, our shift down operation is complete, maintaining the property of the max heap.
### FourγJava Example Code
**Source Package Download:*## src/tutorial/heap/HeapShiftDown.java File Code:
package tutorial.heap;
/**
* Extract an element from the max heap
*/
public class HeapShiftDown{
protected T[] data;
protected int count;
protected int capacity;
// Constructor, construct an empty heap that can hold capacity elements
public HeapShiftDown(int capacity){
//Adding 1 here means the original number of elements that can be stored. Removing index 0, only capacity elements can be stored
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 +10;
T ret = data;
swap(1 , count );
count --;
shiftDown(1);
return ret;
// Get the top element of the max heap
public T getMax(){
assert( count >0);
return data;
}
// Swap the two elements at indices i and j in the heap
private void swap(int i, int j){
T t = data;
data= data;
data= t;
//********************
//* Core Helper Functions for Max Heap
//********************
private void shiftUp(int k){
while( k >1&& data[k/2].compareTo(data)<0){
swap(k, k/2);
k /=2;
}
}
//shiftDown operation
private void shiftDown(int k){
while(2*k <= count ){
int j =2*k;// In this iteration, data and data will be swapped
if( j+10)
j ++;
// data is the maximum value between data[2*k] and data[2*k+1]
if( data.compareTo(data)>=0)break;
swap(k, j);
k = j;
}
System.out.println("shiftDown ended");
}
// Test HeapShiftDown
public static void main(String[] args){
HeapShiftDown heapShiftDown =new HeapShiftDown(100);
// Number of elements in the heap
int N =100;
// Range of element values in the heap [0, M)
int M =100;
for(int i =0; i < N ; i ++)
heapShiftDown.insert(new Integer((int)(Math.random()* M)));
Integer[] arr =new Integer;
// Gradually extract data from the max heap using extractMax
// The extracted order should be from largest to smallest
for(int i =0; i < N ; i ++){
arr= heapShiftDown.extractMax();
System.out.print(arr+" ");
}
// Ensure arr array is sorted from largest to smallest
for(int i =1; i = arr;
}
}