# The Heap Data Structure (C++, Java, C#)

### Review of The Heap Data Structure

I covered heapsort a while ago, and that used a heap as well. A heap is tree based abstract data type that works by maintaining the heap property. Basically, there’s 2 common heap properties: min-heap, and max-heap. Min-heap says that the root of the heap must be the lowest value/priority in the heap, and the successive levels of children are the next smallest. Max-heap, the highest value/priority must be the root, and successive levels of children are the next largest. A heap in itself is a pretty basic priority queue. If an interactive visualization helps you to understand: http://algoviz.org/OpenDSA/Books/OpenDSA/html/Heaps.html.

• Most heaps are implemented using arrays.
• Insertion is done left to right. So, for example, 5 was my root, and I insert 7, then 7 would be the left child, and then I insert 8, 8 would be the right child.
• Children of the node at position n would be at positions 2n (left) and 2n + 1 (right) in a one-based array (where the root resides at index 1 in an array, index 0 is unused).
• In a zero based array, left child is 2n + 1, and right child is 2n + 2.
• Because a heap is a type of priority queue, removing something from a priority queue means also updating the priorities of the elements in the heap.
• The most common example of a heap is called a binary heap, where if illustrated, the data structure looks like a binary tree.
• For this tutorial, we will implement both types of binary heaps: min and max.
• A heap is always complete, in that each level of the heap is populated with children (it looks even in other words)
• Finding the minimum or maximum in a heap is simple: its always the root

### Methods/functions:

• Insert(): inserts into a heap, and we have to call a SiftUp() method that checks the heap correctness and performs necessary fixes
• SiftUp()/SiftDown(): SiftUp is performed after an insertion, to correct the position of the newly inserted value, and restore the heap property. SiftDown() is performed after a removal, and also restores the heap property. Both are recursive.
• BuildHeap(): sometimes also called Heapify(), it builds a heap from a given array, methods such as MinHeapify() or MaxHeapify() are used to build heap
• MaxHeapify(), MinHeapify(): These two methods are used in BuildHeap() and are used to fix the heap and checks for correctness
• Remove(): removes some element from a heap, we also have to call a SiftDown() method that checks the heap correctness and performs necessary fixes
• RemoveMin(): removes the root of a min-heap
• RemoveMax(): removes the root of a max-heap
• GetParentIndex(): returns a parent index of some value, in a one-based heap like so: return index / 2; In a zero-based heap: return index – 1 / 2;

### Pseudo-code for BuildMaxHeap() and MaxHeapify():

BUILD-MAX-HEAP (A)
1     heap-size [A] ←  length [A]
2    for  i ←  ⌊ length [A]/2⌋ downto  1
3             do  MAX-HEAPIFY (A,i)

MAX-HEAPIFY (A,i)
1     l ←  LEFT (i)
2     r ←  RIGHT (i)
3    if  l≤ heap-size [A] and A[l]>A[i]
4          then  largest ←  l
5          else   largest ←  i
6    if  r≤ heap-size [A] and A[r]>A[ largest ]
7          then  largest ←  r
8    if  largest ≠i
9          then Swap A[i] and A[ largest ]
10                       MAX-HEAPIFY (A, largest )

### Pseudo-code for min-heap insertion:

To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up), by following this algorithm:

1. Add the element to the bottom level of the heap (insertion done).
2. Compare the added element with its parent; if they are in the correct order, stop (siftup begins here).
3. If not, swap the element with its parent and return to the previous step (recurse).

### Pseudo-code for min-heap removal:

The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap (also known as bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down, and extract-min/max).

1. Replace the root of the heap with the last element on the last level.
2. Compare the new root with its children; if they are in the correct order, stop.
3. If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)

### Min-Heap Implementation in C# (using zero-based array):

```class Program
{
static void Main(string[] args)
{

MinHeap mh = new MinHeap(7);
mh.insert(8);
mh.insert(5);
mh.insert(10);
mh.insert(3);
mh.insert(1);
mh.insert(7);
mh.insert(20);
Console.WriteLine(mh.getMin());
mh.displayHeap();

mh.removeMin();
Console.WriteLine(mh.getMin());
mh.displayHeap();

mh.remove(7);
Console.WriteLine(mh.getMin());
mh.displayHeap();
int[] arr = {77,64,21,89,92,17,30,42,50,2 };
mh.BuildMinHeap(arr);
mh.displayHeap();
}
}
class MinHeap
{
int[] arr;
int arrSize;//size for the array container
int heapSize;//keeps track of the number of elements
public MinHeap()
{
arrSize = 0;
heapSize = 0;
arr = new int[arrSize];
}
public MinHeap(int size)
{
arr = new int[size];
}
public void setHeapSize(int size)
{
this.arrSize = size;
arr = new int[size];
}
public void insert(int value)
{
if (heapSize == arr.Length)
{
throw new Exception("Heap is at full capacity!");
}
else
{
arr[heapSize] = value;
heapSize++;
siftUp(heapSize - 1);
}
}
public void remove(int value)
{
for (int i = 0; i < heapSize - 1; i++)
{
if (arr[i] == value)
{
arr[i] = arr[heapSize - 1];
heapSize--;
siftDown(i);
break;
}
}
}
public void removeMin()
{
if (heapSize == 0)
{
throw new Exception("Heap is empty!");
}
else
{
arr[0] = arr[heapSize - 1];
heapSize--;
if (heapSize > 0)
{
siftDown(0);
}
}
}
private void siftUp(int index)
{
int parentIndex, temp;
if (index != 0)
{
parentIndex = getParentIndex(index);
if (arr[parentIndex] > arr[index])
{
temp = arr[parentIndex];
arr[parentIndex] = arr[index];
arr[index] = temp;
siftUp(parentIndex);
}
}
}
private int getParentIndex(int index)
{
return (index - 1) / 2;
}
private void siftDown(int nodeIndex)
{
int leftChildIndex, rightChildIndex, minIndex, tmp;

leftChildIndex = getLeftChildIndex(nodeIndex);

rightChildIndex = getRightChildIndex(nodeIndex);

if (rightChildIndex >= heapSize)
{
if (leftChildIndex >= heapSize)
{
return;
}
else
{
minIndex = leftChildIndex;
}
}
else
{
if (arr[leftChildIndex] <= arr[rightChildIndex])
{
minIndex = leftChildIndex;
}
else
{
minIndex = rightChildIndex;
}
}
if (arr[nodeIndex] > arr[minIndex])
{
tmp = arr[minIndex];

arr[minIndex] = arr[nodeIndex];

arr[nodeIndex] = tmp;

siftDown(minIndex);
}
}
private int getRightChildIndex(int nodeIndex)
{
return (2 * nodeIndex) + 2;
}
private int getLeftChildIndex(int nodeIndex)
{
return (2 * nodeIndex) + 1;
}
public void displayHeap()
{
Console.WriteLine("Elements of the heap:");
for (int i = 0; i < heapSize; i++)
{
Console.Write("{0} ", arr[i]);
}

Console.WriteLine("\n***********************************");
}
public int getMin()
{
return arr[0];
}
public void BuildMinHeap(int[] input)
{
if (heapSize > 0)
{
//clear the current heap
Array.Resize(ref arr, input.Length);
heapSize = 0;
for (int i = 0; i < arr.Length; i++)
{
arr[i] = input[i];
heapSize++;
}
}
for (int i = heapSize - 1 / 2; i >= 0; i--)
{
MinHeapify(i);
}
}
private void MinHeapify(int index)
{
int left = 2 * index;
int right = (2 * index) + 1;
int smallest = index;
if (left < heapSize && arr[left] < arr[index])
{
smallest = left;
}
else
{
smallest = index;
}
if (right < heapSize && arr[right] < arr[smallest])
{
smallest = right;
}
if (smallest != index)
{
swap(ref arr, index, smallest);
MinHeapify(smallest);
}
}
private void swap(ref int[] input, int a, int b)
{
int temp = input[a];
input[a] = input[b];
input[b] = temp;
}
public void deleteHeap()
{
Array.Resize(ref arr, 0);
heapSize = 0;
}
}
```