Heap shift up
This section introduces how to add an element to a max heap, calledshift up。
Suppose we add a new element 52 to the max heap below, placing it at the last position of the array. Since 52 is greater than its parent node 16, the heap property is not satisfied, and an adjustment is needed.
First, swap the values at indices 5 and 11 in the array, that is, swap 52 and 16.
At this point, 52 is still greater than the value 41 at parent index 2, so we need to move it further up.
Now compare 52 with 62. Since 52 is already smaller than its parent, it does not need to move up further, and the max heap property is satisfied. We call this process shift up for a max heap.
Java Example Code
Source Code Package Download:Download
src/example/heap/HeapShiftUp.java file code:
package example.heap;
/**
* Add an element to the heap
*/
public class HeapShiftUp<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// Constructor, constructs an empty heap that can hold capacity elements
public HeapShiftUp(int capacity){
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);
}
// 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;
}
}
// 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; // Heap element value range [0, M)
for( int i = 0 ; i < N ; i ++ )
heapShiftUp.insert( new Integer((int)(Math.random() * M)) );
System.out.println(heapShiftUp.size());
}
}
/**
* Add an element to the heap
*/
public class HeapShiftUp<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// Constructor, constructs an empty heap that can hold capacity elements
public HeapShiftUp(int capacity){
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);
}
// 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;
}
}
// 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; // Heap element value range [0, M)
for( int i = 0 ; i < N ; i ++ )
heapShiftUp.insert( new Integer((int)(Math.random() * M)) );
System.out.println(heapShiftUp.size());
}
}