堆结构实现 - 元素码农

发布时间: 2025-03-21 15:35

↑

# 堆结构实现

堆（Heap）是一种特殊的完全二叉树，它满足堆的性质：每个节点的值都大于或等于（或小于或等于）其子节点的值。本文将详细介绍堆的实现原理和应用场景。

## 堆的基本概念

### 定义

堆是一种完全二叉树，分为两种类型：
1. 最大堆：父节点的值总是大于或等于子节点的值
2. 最小堆：父节点的值总是小于或等于子节点的值

### 堆的性质

1. 结构性质
   - 是完全二叉树
   - 从上到下，从左到右填充

2. 堆序性质
   - 最大堆：A[parent(i)] ≥ A[i]
   - 最小堆：A[parent(i)] ≤ A[i]

## 堆的实现

### 基本结构

```go
// 最大堆实现
type MaxHeap struct {
    items []int
}

// 创建新堆
func NewMaxHeap() *MaxHeap {
    return &MaxHeap{items: make([]int, 0)}
}

// 获取父节点索引
func parent(i int) int {
    return (i - 1) / 2
}

// 获取左子节点索引
func leftChild(i int) int {
    return 2*i + 1
}

// 获取右子节点索引
func rightChild(i int) int {
    return 2*i + 2
}
```

### 基本操作

1. 插入元素

```go
// 插入新元素
func (h *MaxHeap) Insert(key int) {
    h.items = append(h.items, key)
    h.heapifyUp(len(h.items) - 1)
}

// 向上调整
func (h *MaxHeap) heapifyUp(index int) {
    for index > 0 {
        parentIdx := parent(index)
        if h.items[parentIdx] < h.items[index] {
            h.items[parentIdx], h.items[index] = h.items[index], h.items[parentIdx]
            index = parentIdx
        } else {
            break
        }
    }
}
```

2. 删除最大元素

```go
// 删除并返回最大元素
func (h *MaxHeap) ExtractMax() (int, error) {
    if len(h.items) == 0 {
        return 0, errors.New("heap is empty")
    }
    
    max := h.items[0]
    lastIdx := len(h.items) - 1
    h.items[0] = h.items[lastIdx]
    h.items = h.items[:lastIdx]
    
    if len(h.items) > 0 {
        h.heapifyDown(0)
    }
    
    return max, nil
}

// 向下调整
func (h *MaxHeap) heapifyDown(index int) {
    maxIndex := index
    size := len(h.items)
    
    for {
        leftIdx := leftChild(index)
        rightIdx := rightChild(index)
        
        if leftIdx < size && h.items[leftIdx] > h.items[maxIndex] {
            maxIndex = leftIdx
        }
        
        if rightIdx < size && h.items[rightIdx] > h.items[maxIndex] {
            maxIndex = rightIdx
        }
        
        if maxIndex == index {
            break
        }
        
        h.items[index], h.items[maxIndex] = h.items[maxIndex], h.items[index]
        index = maxIndex
    }
}
```

### 堆排序

```go
// 堆排序
func HeapSort(arr []int) {
    // 建堆
    for i := len(arr)/2 - 1; i >= 0; i-- {
        heapify(arr, len(arr), i)
    }
    
    // 排序
    for i := len(arr) - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2
    
    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}
```

## 优先队列实现

使用堆实现优先队列是一种常见的应用：

```go
// 优先队列元素
type Item struct {
    value    interface{}
    priority int
}

// 优先队列
type PriorityQueue struct {
    items []*Item
}

// 插入元素
func (pq *PriorityQueue) Enqueue(value interface{}, priority int) {
    item := &Item{value: value, priority: priority}
    pq.items = append(pq.items, item)
    pq.heapifyUp(len(pq.items) - 1)
}

// 获取最高优先级元素
func (pq *PriorityQueue) Dequeue() (interface{}, error) {
    if len(pq.items) == 0 {
        return nil, errors.New("queue is empty")
    }
    
    item := pq.items[0]
    lastIdx := len(pq.items) - 1
    pq.items[0] = pq.items[lastIdx]
    pq.items = pq.items[:lastIdx]
    
    if len(pq.items) > 0 {
        pq.heapifyDown(0)
    }
    
    return item.value, nil
}
```

## 应用场景

1. 优先队列
   - 任务调度系统
   - 事件处理
   - 网络包处理

2. 排序算法
   - 堆排序
   - 部分排序

3. 选择问题
   - 获取第k大/小的元素
   - 数据流中位数

4. 图算法
   - Dijkstra最短路径
   - Prim最小生成树

## 性能分析

### 时间复杂度

1. 插入操作：O(log n)
2. 删除最大/最小元素：O(log n)
3. 获取最大/最小元素：O(1)
4. 建堆：O(n)
5. 堆排序：O(n log n)

### 空间复杂度

1. 存储：O(n)
2. 原地堆排序：O(1)

## 优化技巧

1. 数组预分配
```go
// 预分配空间避免频繁扩容
heap := &MaxHeap{items: make([]int, 0, capacity)}
```

2. 批量建堆
```go
// 自底向上建堆，比逐个插入更高效
func BuildHeap(arr []int) *MaxHeap {
    heap := &MaxHeap{items: arr}
    for i := len(arr)/2 - 1; i >= 0; i-- {
        heap.heapifyDown(i)
    }
    return heap
}
```

3. 懒惰删除
```go
// 标记删除而不是立即物理删除
type Item struct {
    value    int
    deleted  bool
}
```

## 注意事项

1. 索引计算
   - 注意数组边界
   - 正确计算父子节点索引

2. 堆的维护
   - 保持完全二叉树性质
   - 正确处理相等元素

3. 内存管理
   - 及时释放不需要的空间
   - 避免频繁扩容

## 总结

堆是一种重要的数据结构，它在很多场景下都有重要应用，特别是在需要维护数据集最值的场景中。理解堆的实现原理和各种操作的复杂度，对于设计高效的算法和系统非常重要。在实际应用中，要根据具体需求选择合适的堆类型，并注意优化和性能考虑。