Min Heap and Max Heap
A Binary Heap
is a Complete Binary Tree. A binary heap is typically represented as array. The
representation is done as:
§
The root element will be at
Arr[0].
§
Below table shows indexes of
other nodes for the ith node, i.e., Arr[i]:
Arr[i/2]
|
Returns the parent node
|
Arr[(2*i)+1]
|
Returns the left child node
|
Arr[(2*i)+2]
|
Returns the right child node
|
The traversal method use to achieve Array representation is Level Order
Binary Heap satisfies the Ordering Property.
1. Min Heap Property: The value of each node is greater than or
equal to the value of its parent, with the minimum value at the root.
equal to the value of its parent, with the minimum value at the root.
2. Max Heap Property: The value of each node is less than or
equal to the value its parent, with the maximum value at the root.
equal to the value its parent, with the maximum value at the root.
Time Complexity
Operation
|
Binary Heap
|
find-min
|
Θ(1)
|
delete-min
|
Θ(log n)
|
insert
|
O(log n)
|
decrease-key
|
Θ(log n)
|
merge
|
Θ(n)
|
/* Array
implementation of a Heap
5
/ \
6
16
/ \
/ \
50 20 ?
?
*/
/*Property 1 -
Balanced Binary Search Tree
*Property 2 - Every parent key is lower than
* Child Keys */
public class MinHeap {
private int size = 0;
private int capacity = 10;
int items[] = new int[capacity];
int
getLeftChildIndex(int parentIndex) {
return 2 * parentIndex + 1;
}
int
getRightChildIndex(int parentIndex) {
return 2 * parentIndex + 2;
}
int getParentIndex(int childIndex) {
return (childIndex - 1) / 2;
}
int leftChild(int index) {
return items[getLeftChildIndex(index)];
}
int rightChild(int index) {
return items[getRightChildIndex(index)];
}
int parent(int index) {
return items[getParentIndex(index)];
}
boolean hasLeftChild(int index) {
return
getLeftChildIndex(index) < size;
}
boolean hasRightChild(int index) {
return
getRightChildIndex(index) < size;
}
boolean hasParent(int index) {
return getParentIndex(index) >= 0;
private void swap(int indexOne, int indexTwo) {
int temp = items[indexOne];
items[indexOne] = items[indexTwo];
items[indexTwo] = temp;
}
private void
ensureExtraCapacity(){
if(size==capacity){
items = Arrays.copyOf(items, capacity*2);
capacity=capacity*2;
}
}
/* Extract min-heap value from Heap
*
Time Complexity O(1) */
private int peek() {
if (size == 0)
throw new
IllegalStateException();
return items[0];
}
/* Removing top element from
Array/Heap
*
Time Complexity O(logn) */
private int delete() {
if (size == 0)
throw new
IllegalStateException();
int item = items[0];
int index=0;
swap(index, size - 1);
size--;
heapifyDown();
return item;
}
public void heapifyDown() {
int parentIndex = 0;
while (hasLeftChild(parentIndex)) {
int smallerChildIndex =getLeftChildIndex(parentIndex);
if (hasRightChild(parentIndex) && rightChild(parentIndex)
< leftChild(parentIndex))
smallerChildIndex = getRightChildIndex(parentIndex);
if (items[parentIndex] <= items[smallerChildIndex])
break;
else
swap(parentIndex, smallerChildIndex);
parentIndex = smallerChildIndex;
}
}
public int
smalestValueByIndex(int parentIndex,
int leftChildIndex, int rightChildIndex){
if(items[leftChildIndex]< items[parentIndex]
&&
hasRightChild(parentIndex) && items[leftChildIndex]
< items[rightChildIndex] ) {
return leftChildIndex;
}
else if(hasRightChild(parentIndex)
&& items[rightChildIndex]< items[parentIndex]
&&
hasLeftChild(parentIndex) && items[rightChildIndex]
< items[leftChildIndex])
return rightChildIndex;
else
return parentIndex;
}
/* Adding element in a heap/array
*
Time Complexity O(logn)
*/
public void add(int item) {
ensureExtraCapacity();
items[size] = item;
size++;
heapifyUp();
}
public void heapifyUp() {
int index = size - 1;
while (hasParent(index) &&
parent(index) > items[index]) {
swap(getParentIndex(index), index);
index =
getParentIndex(index);
}
}
public static void main(String[] args) {
MinHeap heap = new MinHeap();
/* Inserting elements in a Heap */
heap.add(20); heap.add(6); heap.add(16);
heap.add(50); heap.add(5);
System.out.println("Printing
Array after adding items");
for(int i=0; i<heap.size ; i++)
System.out.print(heap.items[i]+" ");
System.out.println("\nMinimum
Element "+heap.peek());
/*Deleting elements from a heap*/
heap.delete();
System.out.println("Printing
Array after deleting item");
for(int i=0; i<heap.size ; i++)
System.out.print(heap.items[i]+" ");
heap.delete();
System.out.println("Printing
Array after deleting item");
for(int i=0; i<heap.size ; i++)
System.out.print(heap.items[i]+" ");
heap.delete();
System.out.println("Printing
Array after deleting item");
for(int i=0; i<heap.size ; i++)
System.out.print(heap.items[i]+" ");
}
}
Output
Printing
Array after adding items
5 6 16
50 20
Minimum
Element 5
Printing
Array after deleting item
6 20 16
50
Printing
Array after deleting item
16 20
50
Printing
Array after deleting item
20 50
No comments:
Post a Comment