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.

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.
  • 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
Max-Heap with array representation

Max-Heap with array representation

Min-MaxHeaps

Min and Max Heap illustrations/comparison

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

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

 

Advertisements

2 thoughts on “The Heap Data Structure (C++, Java, C#)

  1. Pingback: Priority Queue Tutorial (C#, C++, Java) | Bits and Pieces of Code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s