### 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.

**To refresh your memory:**

**To refresh your memory:**

- 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**.

- In a
- 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:

- Add the element to the bottom level of the heap (insertion done).
- Compare the added element with its parent; if they are in the correct order, stop (siftup begins here).
- 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*).

- Replace the root of the heap with the last element on the last level.
- Compare the new root with its children; if they are in the correct order, stop.
- 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.)

### Max-Heap Implementation in C++

### Min-Heap Implementation in Java

### 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; } }

[…] (or, in an alternative implementation, the least) valued record. Most often implemented using the heap data structure. The name comes from a common application where the records being stored represent tasks, with the […]

LikeLike

Reblogged this on C Programming with Al Jensen.

LikeLike