Heap Shift Down

This section will introduce how to extract an element from a max heap, a process known as shift down. Only the element with the highest priority, which is the root node, can be extracted. After removing the original 62, the following steps explain how to fill the vacancy in the max heap.

First, we place the last element of the array at the root node, which does not satisfy the definition of a max heap.

The adjustment process involves moving the root node, 16, step by step downwards. Since 16 is smaller than its child nodes, we first compare the child nodes 52 and 30 to determine which is larger and swap 16 with the larger one.

Next, we compare 16 with its child nodes 28 and 41. Since 41 is larger, we swap 16 with 41.

Continuing, we compare 16 with its child node 15. Since 16 is larger, no further swaps are needed. The shift down operation is now complete, maintaining the properties of a max heap.

Four, Java Example Code

Source Code Download: Download

src/tutorialpro/heap/HeapShiftDown.java File Code:

package tutorialpro.heap;

/**
 * Extracting an element from a max heap
 */
public class HeapShiftDown<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // Constructor, creates an empty heap with capacity for 'capacity' elements
    public HeapShiftDown(int capacity){
        // Adding 1 accounts for the original number of elements, so it can hold 'capacity' elements excluding the 0th index
        data = (T[])new Comparable[capacity+1];
        count = 0;
        this.capacity = capacity;
    }
    // Returns the number of elements in the heap
    public int size(){
        return count;
    }
    // Returns a boolean indicating whether the heap is empty
    public boolean isEmpty(){
        return count == 0;
    }
    // Inserts a new element into the max heap
    public void insert(T item){

        assert count + 1 <= capacity;
        data[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // Extracts the top element from the max heap, which is the largest element
    public T extractMax(){
        assert count > 0;
        T ret = data[1];
        swap( 1 , count );
        count --;
        shiftDown(1);
        return ret;
    }
    // Retrieves the top element of the max heap
    public T getMax(){
        assert( count > 0 );
        return data[1];
    }
    // Swaps two elements in the heap at indices i and j
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //********************
    //* Core auxiliary function for max heap
    //********************
    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, data[k] and data[j] swap positions

if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
    j ++;
// data[j] is the maximum value between 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 ends");
}

// Test HeapShiftDown
public static void main(String[] args) {
HeapShiftDown<Integer> heapShiftDown = new HeapShiftDown<Integer>(100);
// Number of elements in the heap
int N = 100;
// Range of 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[N];
// Gradually extract data from the max heap using extractMax
// The order of extraction should be from largest to smallest
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapShiftDown.extractMax();
System.out.print(arr[i] + " ");
}
// Ensure that the arr array is sorted in descending order
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}
}