Heap Data Structure and Its Operation in C-Sharip

Back to: Data Structure Tutorial

A heap is a specialized tree-based data structure where the value of each node is greater than or equal to (for a max-heap) or less than or equal to (for a min-heap) the values of its children. Heaps are commonly used to implement priority queues and in sorting algorithms like heapsort.

In C#, we can implement a heap using an array, where the left child of a node at index i is at index 2i + 1, and the right child is at index 2i + 2. Here’s an example implementation of a min-heap:

public class MinHeap
{
    private int[] heap;
    private int size;

    public MinHeap(int capacity)
    {
        heap = new int[capacity];
        size = 0;
    }

    // Get the index of the parent node
    private int Parent(int index)
    {
        return (index - 1) / 2;
    }

    // Get the index of the left child node
    private int LeftChild(int index)
    {
        return 2 * index + 1;
    }

    // Get the index of the right child node
    private int RightChild(int index)
    {
        return 2 * index + 2;
    }

    // Swap the values at the given indices
    private void Swap(int index1, int index2)
    {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

    // Insert a value into the heap
    public void Insert(int value)
    {
        if (size == heap.Length)
        {
            throw new IndexOutOfRangeException("Heap is full");
        }

        heap[size] = value;
        int current = size;
        size++;

        // Bubble up the new value to its correct position
        while (current > 0 && heap[current] < heap[Parent(current)])
        {
            Swap(current, Parent(current));
            current = Parent(current);
        }
    }

    // Remove and return the minimum value in the heap
    public int RemoveMin()
    {
        if (size == 0)
        {
            throw new IndexOutOfRangeException("Heap is empty");
        }

        int min = heap[0];
        size--;
        heap[0] = heap[size];

        // Bubble down the new root value to its correct position
        int current = 0;
        while (LeftChild(current) < size)
        {
            int minChild = LeftChild(current);
            if (RightChild(current) < size && heap[RightChild(current)] < heap[minChild])
            {
                minChild = RightChild(current);
            }

            if (heap[current] <= heap[minChild])
            {
                break;
            }

            Swap(current, minChild);
            current = minChild;
        }

        return min;
    }
}

With this implementation, we can create a new min-heap with a specified capacity, insert values into the heap using the Insert method, and remove the minimum value using the RemoveMin method.