堆

​堆（Heap）详解与 C# 实现​

堆是一种完全二叉树数据结构，满足以下性质：

• ​最大堆​：父节点值 ≥ 子节点值（堆顶为最大值）。

• ​最小堆​：父节点值 ≤ 子节点值（堆顶为最小值）。

​1. 核心操作与复杂度​

​​(1) 创建堆（Heapify）​​

• ​操作​：将无序数组调整为堆结构。

• ​时间复杂度​：​O(n)​​（自底向上调整，非 O(n log n)）。

• ​空间复杂度​：​O(1)​​（原地调整）。

• ​稳定性​：不涉及稳定性。

​​(2) 插入元素（Insert）​​

• ​操作​：将新元素放入堆末尾，然后上浮到正确位置。

• ​时间复杂度​：​O(log n)​。

• ​空间复杂度​：​O(1)​。

• ​稳定性​：不涉及稳定性。

​​(3) 删除堆顶元素（ExtractMax/ExtractMin）​​

• ​操作​：移除堆顶元素，将末尾元素移到堆顶，然后下沉。

• ​时间复杂度​：​O(log n)​。

• ​空间复杂度​：​O(1)​。

• ​稳定性​：不涉及稳定性。

​​(4) 堆排序（Heap Sort）​​

• ​操作​：

  1. 构建堆（O(n)）。

  2. 重复交换堆顶和末尾元素并调整堆（O(n log n)）。

• ​时间复杂度​：​O(n log n)​。

• ​空间复杂度​：​O(1)​​（原地排序）。

• ​稳定性​：​不稳定​（交换操作可能破坏相同值的顺序）。

​2. C# 实现（最大堆）​​

using System;

public class MaxHeap
{
    private int[] heap;
    private int size;
    private int capacity;

    public MaxHeap(int capacity)
    {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    // 创建堆：O(n)
    public void BuildHeap(int[] arr)
    {
        if (arr.Length > capacity)
            throw new ArgumentException("Array exceeds heap capacity.");
        
        Array.Copy(arr, heap, arr.Length);
        size = arr.Length;

        // 从最后一个非叶子节点开始下沉
        for (int i = size / 2 - 1; i >= 0; i--)
        {
            SiftDown(i);
        }
    }

    // 插入元素：O(log n)
    public void Insert(int val)
    {
        if (size == capacity)
            throw new OverflowException("Heap is full.");
        
        heap[size] = val;
        SiftUp(size);
        size++;
    }

    // 删除堆顶：O(log n)
    public int ExtractMax()
    {
        if (size == 0)
            throw new InvalidOperationException("Heap is empty.");
        
        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        SiftDown(0);
        return max;
    }

    // 堆排序：O(n log n)
    public void HeapSort(int[] arr)
    {
        BuildHeap(arr);
        for (int i = size - 1; i > 0; i--)
        {
            Swap(0, i);
            size--;
            SiftDown(0);
        }
        size = arr.Length; // 恢复堆大小
    }

    // 上浮操作
    private void SiftUp(int index)
    {
        while (index > 0)
        {
            int parent = (index - 1) / 2;
            if (heap[index] > heap[parent])
            {
                Swap(index, parent);
                index = parent;
            }
            else
            {
                break;
            }
        }
    }

    // 下沉操作
    private void SiftDown(int index)
    {
        while (true)
        {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int largest = index;

            if (left < size && heap[left] > heap[largest])
                largest = left;
            if (right < size && heap[right] > heap[largest])
                largest = right;

            if (largest != index)
            {
                Swap(index, largest);
                index = largest;
            }
            else
            {
                break;
            }
        }
    }

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

    // 打印堆
    public void PrintHeap()
    {
        for (int i = 0; i < size; i++)
        {
            Console.Write(heap[i] + " ");
        }
        Console.WriteLine();
    }
}

​3. 测试代码​

public class Program
{
    public static void Main()
    {
        int[] arr = { 4, 10, 3, 5, 1 };
        MaxHeap maxHeap = new MaxHeap(arr.Length);

        // 创建堆
        maxHeap.BuildHeap(arr);
        Console.Write("构建后的堆：");
        maxHeap.PrintHeap(); // 输出：10 5 3 4 1

        // 插入元素
        maxHeap.Insert(7);
        Console.Write("插入7后的堆：");
        maxHeap.PrintHeap(); // 输出：10 7 3 4 1 5

        // 删除堆顶
        int max = maxHeap.ExtractMax();
        Console.WriteLine("删除的堆顶元素：" + max); // 输出：10
        Console.Write("删除后的堆：");
        maxHeap.PrintHeap(); // 输出：7 5 3 4 1

        // 堆排序
        int[] arrToSort = { 12, 11, 13, 5, 6, 7 };
        maxHeap.HeapSort(arrToSort);
        Console.Write("堆排序结果：");
        foreach (int num in arrToSort)
        {
            Console.Write(num + " "); // 输出：5 6 7 11 12 13（升序）
        }
    }
}

​4. 关键总结​

​适用场景​：优先队列、Top K 问题、堆排序（无需额外空间但不稳定）。