Heap Shift Up

This section introduces how to add an element to a max-heap, a process known as shift up.

Suppose we add a new element 52 to the following max-heap, placing it at the end of the array. Since 52 is greater than its parent node 16, this violates the heap's definition and requires adjustment.

First, swap the values at indices 5 and 11 in the array, which means swapping 52 and 16.

At this point, 52 is still larger than its parent node at index 2, which is 41, so further adjustments are needed.

Next, compare 52 and 62. Since 52 is now smaller than its parent node, it no longer needs to move up and satisfies the max-heap definition. This process is referred to as max-heap shift up.

Java Example Code

Source Code Download: Download

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

package tutorialpro.heap;

/**
 * Adding an element to the heap
 */
public class HeapShiftUp<T extends Comparable> {

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

    // Constructor, creates an empty heap with capacity for 'capacity' elements
    public HeapShiftUp(int capacity) {
        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 'item' into the max-heap
    public void insert(T item) {
        assert count + 1 <= capacity;
        data[count + 1] = item;
        count++;
        shiftUp(count);
    }

    // Swaps the 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;
    }

    //********************
    //* Core helper 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;
        }
    }

    // Test HeapShiftUp
    public static void main(String[] args) {
        HeapShiftUp<Integer> heapShiftUp = new HeapShiftUp<Integer>(100);
        int N = 50; // Number of elements in the heap
        int M = 100; // Range of element values [0, M)
        for (int i = 0; i < N; i++)
            heapShiftUp.insert(new Integer((int) (Math.random() * M)));
        System.out.println(heapShiftUp.size());
    }
}