chatgpt heap data strucure

Heap is a specialized tree-based data structure that satisfies the heap property: if A is a parent node of B then the key of node A is either greater than or equal to (in a Max Heap) or less than or equal to (in a Min Heap) the key of node B.
Heaps are commonly used to implement priority queues, where the node with the highest (or lowest) priority is always at the front (or root) of the queue. They can also be used for efficient sorting algorithms, such as Heapsort.


In C#, a heap data structure can be implemented using arrays, linked lists, or classes. Here's an example of how to implement a Max Heap using a class in C#:

class MaxHeap
{
    private List<int> heap;

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

    private int Parent(int i)
    {
        return (i - 1) / 2;
    }

    private int LeftChild(int i)
    {
        return (2 * i) + 1;
    }

    private int RightChild(int i)
    {
        return (2 * i) + 2;
    }

    private void Swap(int i, int j)
    {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private void HeapifyUp(int i)
    {
        while (i > 0 && heap[Parent(i)] < heap[i])
        {
            Swap(i, Parent(i));
            i = Parent(i);
        }
    }

    private void HeapifyDown(int i)
    {
        int maxIndex = i;
        int l = LeftChild(i);
        int r = RightChild(i);

        if (l < heap.Count && heap[l] > heap[maxIndex])
        {
            maxIndex = l;
        }

        if (r < heap.Count && heap[r] > heap[maxIndex])
        {
            maxIndex = r;
        }

        if (i != maxIndex)
        {
            Swap(i, maxIndex);
            HeapifyDown(maxIndex);
        }
    }

    public void Insert(int key)
    {
        heap.Add(key);
        HeapifyUp(heap.Count - 1);
    }

    public int ExtractMax()
    {
        int max = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        HeapifyDown(0);
        return max;
    }
}

This implementation provides methods to insert, extract the maximum element (root), and maintain the max-heap property.