YouTipHeap Shift Up
# Heap Shift Up
This section introduces how to add an element to a max-heap, a process called **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, the heap property is violated and needs adjustment.
!(#)
First, we swap the values at indices 5 and 11 in the array, meaning 52 and 16 swap positions.
!(#)
Now, 52 is still greater than its parent node at index 2, which has the value 41. We need to move it further up.
!(#)
At this point, we compare 52 with 62. Since 52 is now smaller than its parent, it no longer needs to move up, and the max-heap property is satisfied. We call this process the **shift up** of a max-heap.
### Java Example Code
**Source Code Package Download:*## src//heap/HeapShiftUp.java File Code:
package .heap;
/**
* Add an element to the heap
*/
public class HeapShiftUp{
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 value 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 +11&& data[k/2].compareTo(data)<0){
swap(k, k/2);
k /=2;
}
}
// Test HeapShiftUp
public static void main(String[] args){
HeapShiftUp heapShiftUp =new HeapShiftUp(100);
int N =50;// Number of elements in the heap
int M =100;// Value range of elements in the heap [0, M)
for(int i =0; i < N ; i ++)
heapShiftUp.insert(new Integer((int)(Math.random()* M)));
System.out.println(heapShiftUp.size());
}
}