How to implement Heap data structure in C#?

How to Implement a Heap Data Structure in C#

A heap is a specialized tree-based data structure that satisfies the heap property. For a max-heap, each parent node is greater than or equal to its child nodes, and for a min-heap, each parent node is less than or equal to its child nodes. Heaps are commonly implemented using arrays.

Below is an example implementation of a min-heap in C#.

Min-Heap Implementation in C#

Heap Class

Here is a simple implementation of a min-heap in C# using an array (or List<T> for dynamic resizing).

using System;
using System.Collections.Generic;

public class MinHeap
{
    private List<int> heap;

    public MinHeap()
    {
        heap = new List<int>();
    }

    public int Count => heap.Count;

    // Add an element to the heap
    public void Add(int value)
    {
        heap.Add(value);
        HeapifyUp(heap.Count - 1);
    }

    // Remove and return the minimum element from the heap
    public int RemoveMin()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty.");

        int minValue = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        HeapifyDown(0);

        return minValue;
    }

    // Peek the minimum element without removing it
    public int PeekMin()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty.");

        return heap[0];
    }

    // Heapify up to maintain heap property
    private void HeapifyUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (heap[index] >= heap[parentIndex])
                break;

            Swap(index, parentIndex);
            index = parentIndex;
        }
    }

    // Heapify down to maintain heap property
    private void HeapifyDown(int index)
    {
        while (index < heap.Count)
        {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int smallestIndex = index;

            if (leftChildIndex < heap.Count && heap[leftChildIndex] < heap[smallestIndex])
                smallestIndex = leftChildIndex;

            if (rightChildIndex < heap.Count && heap[rightChildIndex] < heap[smallestIndex])
                smallestIndex = rightChildIndex;

            if (smallestIndex == index)
                break;

            Swap(index, smallestIndex);
            index = smallestIndex;
        }
    }

    // Swap two elements in the heap
    private void Swap(int index1, int index2)
    {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}

Example Usage

Here's how you can use the MinHeap class:

public class Program
{
    public static void Main()
    {
        MinHeap minHeap = new MinHeap();
        minHeap.Add(10);
        minHeap.Add(4);
        minHeap.Add(15);
        minHeap.Add(20);
        minHeap.Add(0);

        Console.WriteLine("Min element: " + minHeap.PeekMin()); // Output: 0

        Console.WriteLine("Removed Min: " + minHeap.RemoveMin()); // Output: 0
        Console.WriteLine("New Min element: " + minHeap.PeekMin()); // Output: 4

        minHeap.Add(1);
        Console.WriteLine("Min element after adding 1: " + minHeap.PeekMin()); // Output: 1
    }
}

Explanation

1. Heap Structure:

   • The heap is represented as a List<int>. This allows dynamic resizing.
   • The heap property is maintained where each parent node is less than or equal to its children.

2. Add Operation:

   • The new element is added to the end of the list.
   • The HeapifyUp method is called to restore the heap property by comparing the new element with its parent and swapping if necessary.

3. RemoveMin Operation:

   • The minimum element (root of the heap) is removed.
   • The last element in the list is moved to the root position.
   • The HeapifyDown method is called to restore the heap property by comparing the new root with its children and swapping if necessary.

4. PeekMin Operation:

   • Returns the minimum element (root of the heap) without removing it.

5. HeapifyUp and HeapifyDown:

   • These methods ensure the heap property is maintained after insertion or deletion.
   • HeapifyUp is used after insertion to move the new element to its correct position.
   • HeapifyDown is used after deletion to move the new root element to its correct position.

Summary

• Min-Heap: A binary heap where the parent node is always less than or equal to its child nodes.
• Operations: Efficient insertions and deletions with average and worst-case time complexities of O(log n).
• Implementation: Uses a list to dynamically store heap elements, with methods to maintain the heap property after modifications.

This implementation provides a basic yet functional min-heap. For more in-depth knowledge and practical examples on data structures and other programming concepts, consider exploring Grokking the Coding Interview on DesignGurus.io, which provides comprehensive courses on essential coding and interview techniques.