Skip to content

C# – Binary max-heap implementation

February 16, 2012

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) – Wikipedia

The heap data structure is not the same as the storage used for garbage collection(heap).

This article is an introduction to a binary heap.

A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
The heap property: each node is greater than or equal to each of its children according to a comparison predicate defined for the data structure.

Heaps with a mathematical “greater than or equal to” comparison function are called max-heaps; those with a mathematical “less than or equal to” comparison function are called min-heaps. Min-heaps are often used to implement priority queues – Wikipedia .

The binary heap is a special case of the d-ary heap in which d = 2.

MIT recitation, summary of heap operation algorithms:

1 . BUILD-MAX-HEAP – runs in linear time, resultant max-heap from an unordered input array.
2 . MAX-HEAPIFY – maintains heap property and runs in O(lg n) time.
3 . MAX-HEAP-INSERT – O(lg n)
4 . HEAP-EXTRACT-MAX – O(lg n)
5 . HEAP-INCREASE-DECREASE-KEY – O(lg n)

Since we build a heap array, note that for any given node i (starts from zero), its children would be found at 2i + 1 and 2i + 2 index of the array. – Heap implementation using arrays

Some points to remember:

For a heap of height h the minimum number of elements is 2h
and the maximum number of elements is 2h+1− 1.

A array sorted from lowest to highest is a min-heap

minimum value of max heap in an array can be found from the values of array[i+1] to array[n] where Leaf nodes of the max heap or n-element heap are found from index i+1 to n. Here i=n/2; n is array length.

There is no effect calling MAX-HEAPIFY(A, i) for i > size[A]/2 as all the nodes leaf nodes.

There are at most ceil(n/2h+1) nodes of height h in an n-element heap.

Another approach to implement heap is to actually build a binary tree. However this is weakly ordered since heaps do not have a strong ordering policy like a binary search tree. We can use binary numbers to represent path from root to a node to keep track of the nodes and for traversing and this is tedious.

So the most popular implementation is to use an array and visualize the array as a complete binary tree.

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace HeapDemo
{
    class Node
    {
        private int nodeItem; 
        public Node(int value) 
        { nodeItem = value; }
        public int getvalue()
        { return nodeItem; }
        public void setvalue(int id)
        { nodeItem = id; }
    }

    class Heap
    {
        private Node[] heapArray;
        private int maxSize; 
        private int currentSize; 
        public Heap(int maxHeapSize)
        {
            maxSize = maxHeapSize;
            currentSize = 0;
            heapArray = new Node[maxSize]; 
        }
        public bool IsEmpty()
        { return currentSize==0; }
        public bool Insert(int value)
        {
            if(currentSize==maxSize)
                return false;
            Node newNode = new Node(value);
            heapArray[currentSize] = newNode;
            CascadeUp(currentSize++);
            return true;
        } 
        public void CascadeUp(int index)
        {
            int parent = (index-1) / 2;
            Node bottom = heapArray[index];
            while( index > 0 && heapArray[parent].getvalue() < bottom.getvalue() )
            {
                heapArray[index] = heapArray[parent]; 
                index = parent;
                parent = (parent-1) / 2;
            }
            heapArray[index] = bottom;
        } 
        public Node Remove() // Remove maximum value node
        { 
            Node root = heapArray[0];
            heapArray[0] = heapArray[--currentSize];
            CascadeDown(0);
            return root;
        } 
        public void CascadeDown(int index)
        {
            int largerChild;
            Node top = heapArray[index]; 
            while(index < currentSize/2) 
            { 
                int leftChild = 2*index+1;
                int rightChild = leftChild+1;
                if(rightChild < currentSize && heapArray[leftChild].getvalue() < heapArray[rightChild].getvalue())
                    largerChild = rightChild;
                else
                    largerChild = leftChild;
                if( top.getvalue() >= heapArray[largerChild].getvalue() )
                    break;
                heapArray[index] = heapArray[largerChild];
                index = largerChild;
            }
            heapArray[index] = top;
        } 
        public bool HeapIncreaseDecreaseKey(int index, int newValue)
        {
            if(index<0 || index>=currentSize)
                return false;
            int oldValue = heapArray[index].getvalue(); 
            heapArray[index].setvalue(newValue); 
            if(oldValue < newValue) 
                CascadeUp(index); 
            else 
                CascadeDown(index); 
            return true;
        } 
        public void DisplayHeap()
        {
            Console.WriteLine();
            Console.Write("Elements of the Heap Array are : ");
            for(int m=0; m<currentSize; m++)
                if(heapArray[m] != null)
                    Console.Write( heapArray[m].getvalue() + " ");
                else
                    Console.Write( "-- ");
            Console.WriteLine();
            int emptyLeaf = 32;
            int itemsPerRow = 1;
            int column = 0;
            int j = 0; 
            String separator = "...............................";
            Console.WriteLine(separator+separator); 
            while(currentSize > 0) 
            {
                if(column == 0) 
                    for(int k=0; k<emptyLeaf; k++) 
                        Console.Write(' ');
                Console.Write(heapArray[j].getvalue());

                if(++j == currentSize) 
                    break;
                if(++column==itemsPerRow)
                {
                    emptyLeaf /= 2; 
                    itemsPerRow *= 2; 
                    column = 0;
                    Console.WriteLine(); 
                }
                else 
                    for(int k=0; k<emptyLeaf*2-2; k++)
                        Console.Write(' '); 
            } 
            Console.WriteLine("\n"+separator+separator); 
        } 
    } 
    class Program
    {
        public static void Main(String[] args)
        {
            Heap theHeap = new Heap(21); 
            theHeap.Insert(40); 
            theHeap.Insert(70);
            theHeap.Insert(20);
            theHeap.Insert(60);
            theHeap.Insert(50);
            theHeap.Insert(100);
            theHeap.Insert(82);
            theHeap.Insert(35);
            theHeap.Insert(90);
            theHeap.Insert(10);
            theHeap.DisplayHeap();

            Console.WriteLine("Inserting a new node with value 120");
            theHeap.Insert(120);
            theHeap.DisplayHeap();

            Console.WriteLine("Removing max element");
            theHeap.Remove();
            theHeap.DisplayHeap();

            Console.WriteLine("Changing root to 130");
            theHeap.HeapIncreaseDecreaseKey(0, 130);
            theHeap.DisplayHeap();

            Console.WriteLine("Changing root to 5");
            theHeap.HeapIncreaseDecreaseKey(0, 5);
            theHeap.DisplayHeap();
            Console.ReadLine();
        }
    } 
}

OUTPUT:

About these ads

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

%d bloggers like this: