手写堆（大顶堆/小顶堆）的实现

题目描述
手写堆的实现要求我们理解堆数据结构的核心原理，并能够用代码实现堆的基本操作。堆是一种特殊的完全二叉树，满足堆性质：每个节点的值都大于等于（大顶堆）或小于等于（小顶堆）其子节点的值。主要操作包括插入元素（offer）、删除堆顶元素（poll）和查看堆顶元素（peek）。

解题过程

1. 理解堆的存储结构
堆通常使用数组来存储，利用完全二叉树的特性可以快速定位父子节点。

• 对于数组中索引为 i 的节点：
  • 其父节点索引为 (i - 1) / 2（向下取整）。
  • 其左子节点索引为 2 * i + 1。
  • 其右子节点索引为 2 * i + 2。
• 示例：根节点（索引0）的左子节点是索引1，右子节点是索引2。

2. 定义堆类的基本结构
我们以最小堆为例，最大堆的实现逻辑类似（比较方向相反）。

public class MinHeap {
    private int[] heap; // 存储堆元素的数组
    private int capacity; // 堆的最大容量
    private int size; // 当前堆中元素的数量

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

3. 实现核心辅助方法：heapifyUp 和 heapifyDown

• heapifyUp（上浮）：当在堆底插入新元素后，可能破坏堆结构，需要将该元素向上移动，直到满足堆性质。

  1. 比较当前节点与其父节点的值。
  2. 如果当前节点值小于父节点值（最小堆），则交换它们。
  3. 重复步骤1-2，直到当前节点大于等于父节点或到达根节点。

  private void heapifyUp(int index) {
      while (index > 0) {
          int parentIndex = (index - 1) / 2;
          if (heap[index] >= heap[parentIndex]) break; // 满足堆性质，退出
          swap(index, parentIndex); // 交换当前节点与父节点
          index = parentIndex; // 继续向上检查
      }
  }
  

• heapifyDown（下沉）：当删除堆顶元素后，将堆底元素移至堆顶，可能破坏堆结构，需要将该元素向下移动。

  1. 比较当前节点与其左右子节点中的较小值（最小堆）。
  2. 如果当前节点值大于该较小值，则交换它们。
  3. 重复步骤1-2，直到当前节点小于等于子节点或没有子节点。

  private void heapifyDown(int index) {
      while (index < size) {
          int leftChild = 2 * index + 1;
          int rightChild = 2 * index + 2;
          int smallest = index; // 假设当前节点是最小值
  
          // 找出当前节点、左子节点、右子节点中的最小值
          if (leftChild < size && heap[leftChild] < heap[smallest]) {
              smallest = leftChild;
          }
          if (rightChild < size && heap[rightChild] < heap[smallest]) {
              smallest = rightChild;
          }
  
          if (smallest == index) break; // 当前节点已是最小，无需下沉
          swap(index, smallest);
          index = smallest; // 继续向下检查
      }
  }
  

4. 实现基本操作

• 插入元素（offer）：

  1. 将新元素放入数组末尾（堆底）。
  2. 增加堆大小 size。
  3. 对末尾索引调用 heapifyUp，恢复堆性质。

  public void offer(int value) {
      if (size == capacity) throw new IllegalStateException("Heap is full");
      heap[size] = value; // 放入末尾
      heapifyUp(size); // 上浮调整
      size++;
  }
  

• 删除堆顶元素（poll）：

  1. 保存堆顶元素（返回值）。
  2. 将堆底元素移至堆顶，并减少 size。
  3. 对堆顶（索引0）调用 heapifyDown，恢复堆性质。

  public int poll() {
      if (size == 0) throw new IllegalStateException("Heap is empty");
      int root = heap[0]; // 保存堆顶
      heap[0] = heap[size - 1]; // 将堆底元素移至堆顶
      size--;
      heapifyDown(0); // 下沉调整
      return root;
  }
  

• 查看堆顶元素（peek）：

  public int peek() {
      if (size == 0) throw new IllegalStateException("Heap is empty");
      return heap[0];
  }
  

5. 完整代码示例

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

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

    public void offer(int value) {
        if (size == capacity) throw new IllegalStateException("Heap is full");
        heap[size] = value;
        heapifyUp(size);
        size++;
    }

    public int poll() {
        if (size == 0) throw new IllegalStateException("Heap is empty");
        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return root;
    }

    public int peek() {
        if (size == 0) throw new IllegalStateException("Heap is empty");
        return heap[0];
    }

    private void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[index] >= heap[parent]) break;
            swap(index, parent);
            index = parent;
        }
    }

    private void heapifyDown(int index) {
        while (index < size) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int smallest = index;
            if (left < size && heap[left] < heap[smallest]) smallest = left;
            if (right < size && heap[right] < heap[smallest]) smallest = right;
            if (smallest == index) break;
            swap(index, smallest);
            index = smallest;
        }
    }

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

关键点总结

• 堆通过数组存储，利用父子节点索引关系实现高效操作。
• heapifyUp 和 heapifyDown 是维护堆性质的核心，时间复杂度均为 O(log n)。
• 插入和删除操作的时间复杂度为 O(log n)，查看堆顶为 O(1)。
• 实际应用中，堆常用于优先队列、Top K 问题等场景。