堆排序 - 元素码农

发布时间: 2025-03-21 18:46

↑

# 堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。它通过构建最大堆（或最小堆），然后重复从堆顶取出最大（或最小）元素并调整堆结构的方式来进行排序。

## 基本原理

1. 构建最大堆（升序）或最小堆（降序）
2. 交换堆顶元素（最大/最小值）到数组末尾
3. 调整剩余元素重新成为合法的堆
4. 重复步骤2-3直到堆为空

## 动画演示

```
初始数组：[ 4 10 3 5 1 ]

构建最大堆：
       10
      /  \
     5    3
    / \
   4   1

第一次交换和调整：
[ 4 5 3 1 | 10 ]
       5
      /  \
     4    3
    /
   1

第二次交换和调整：
[ 4 1 3 | 5 10 ]
       4
      /  \
     1    3

第三次交换和调整：
[ 1 3 | 4 5 10 ]
       3
      /
     1

第四次交换和调整：
[ 1 | 3 4 5 10 ]

最终结果：
[ 1 3 4 5 10 ]
```

## 代码实现

### 基本实现

```python
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 比较左子节点
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 比较右子节点
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # 如果最大值不是根节点，则交换并继续调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    
    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 一个个从堆顶取出元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr

# 使用示例
arr = [12, 11, 13, 5, 6, 7]
print("排序前:", arr)
heap_sort(arr)
print("排序后:", arr)
```

### 迭代版本

```python
def heapify_iterative(arr, n, i):
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < n and arr[left] > arr[largest]:
            largest = left
        
        if right < n and arr[right] > arr[largest]:
            largest = right
        
        if largest == i:
            break
        
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

def heap_sort_iterative(arr):
    n = len(arr)
    
    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify_iterative(arr, n, i)
    
    # 一个个从堆顶取出元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify_iterative(arr, i, 0)
    
    return arr

# 使用示例
arr = [12, 11, 13, 5, 6, 7]
print("排序前:", arr)
heap_sort_iterative(arr)
print("排序后:", arr)
```

### 优化版本

```python
class HeapSort:
    def __init__(self):
        self.heap_size = 0
    
    def parent(self, i):
        return (i - 1) >> 1
    
    def left(self, i):
        return (i << 1) + 1
    
    def right(self, i):
        return (i << 1) + 2
    
    def build_max_heap(self, arr):
        self.heap_size = len(arr)
        for i in range(self.heap_size // 2 - 1, -1, -1):
            self._max_heapify(arr, i)
    
    def _max_heapify(self, arr, i):
        while True:
            largest = i
            l = self.left(i)
            r = self.right(i)
            
            # 使用条件表达式简化比较
            largest = l if l < self.heap_size and arr[l] > arr[largest] else largest
            largest = r if r < self.heap_size and arr[r] > arr[largest] else largest
            
            if largest == i:
                break
            
            # 使用异或交换，避免使用临时变量
            arr[i] ^= arr[largest]
            arr[largest] ^= arr[i]
            arr[i] ^= arr[largest]
            
            i = largest
    
    def sort(self, arr):
        if len(arr) <= 1:
            return arr
        
        # 构建最大堆
        self.build_max_heap(arr)
        
        # 从末尾开始，将最大值放到正确位置
        for i in range(len(arr) - 1, 0, -1):
            # 使用异或交换
            arr[0] ^= arr[i]
            arr[i] ^= arr[0]
            arr[0] ^= arr[i]
            
            self.heap_size -= 1
            self._max_heapify(arr, 0)
        
        return arr

# 使用示例
sorter = HeapSort()
arr = [12, 11, 13, 5, 6, 7]
print("排序前:", arr)
sorter.sort(arr)
print("排序后:", arr)
```

## 性能分析

### 时间复杂度

- 构建堆：O(n)
- 调整堆：O(log n)
- 整体：O(n log n)

### 空间复杂度

- O(1)，原地排序算法

### 稳定性

- 不稳定排序算法
- 相等元素的相对位置可能改变

## 优缺点

### 优点

1. 时间复杂度稳定
2. 空间复杂度低
3. 适合处理大数据量
4. 可以用于优先队列

### 缺点

1. 不稳定排序
2. 对于完全有序的数据，性能不如快速排序
3. 数据量较小时，性能不如插入排序

## 应用场景

1. 优先队列实现
2. 大数据量排序
3. 求第k大/小的数
4. 多路归并

## 实际应用示例

### 1. 优先队列实现

```python
class PriorityQueue:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) >> 1
    
    def left(self, i):
        return (i << 1) + 1
    
    def right(self, i):
        return (i << 1) + 2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def heapify_up(self, i):
        parent = self.parent(i)
        if i > 0 and self.heap[i] > self.heap[parent]:
            self.swap(i, parent)
            self.heapify_up(parent)
    
    def heapify_down(self, i):
        largest = i
        left = self.left(i)
        right = self.right(i)
        
        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        
        if largest != i:
            self.swap(i, largest)
            self.heapify_down(largest)
    
    def push(self, item):
        self.heap.append(item)
        self.heapify_up(len(self.heap) - 1)
    
    def pop(self):
        if not self.heap:
            return None
        
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.heapify_down(0)
        
        return root
    
    def peek(self):
        return self.heap[0] if self.heap else None
    
    def size(self):
        return len(self.heap)

# 使用示例
pq = PriorityQueue()
pq.push(3)
pq.push(1)
pq.push(4)
pq.push(1)
pq.push(5)

print("优先队列内容:")
while pq.size() > 0:
    print(pq.pop())
```

### 2. 任务调度器

```python
from dataclasses import dataclass
from typing import Any

@dataclass
class Task:
    priority: int
    data: Any
    timestamp: float
    
    def __lt__(self, other):
        if self.priority != other.priority:
            return self.priority > other.priority
        return self.timestamp < other.timestamp

class TaskScheduler:
    def __init__(self):
        self.tasks = []
    
    def _heapify_up(self, pos):
        parent = (pos - 1) // 2
        while pos > 0 and self.tasks[pos] < self.tasks[parent]:
            self.tasks[pos], self.tasks[parent] = self.tasks[parent], self.tasks[pos]
            pos = parent
            parent = (pos - 1) // 2
    
    def _heapify_down(self, pos):
        size = len(self.tasks)
        while True:
            min_pos = pos
            left = 2 * pos + 1
            right = 2 * pos + 2
            
            if left < size and self.tasks[left] < self.tasks[min_pos]:
                min_pos = left
            if right < size and self.tasks[right] < self.tasks[min_pos]:
                min_pos = right
            
            if min_pos == pos:
                break
            
            self.tasks[pos], self.tasks[min_pos] = self.tasks[min_pos], self.tasks[pos]
            pos = min_pos
    
    def add_task(self, task):
        self.tasks.append(task)
        self._heapify_up(len(self.tasks) - 1)
    
    def get_next_task(self):
        if not self.tasks:
            return None
        
        if len(self.tasks) == 1:
            return self.tasks.pop()
        
        task = self.tasks[0]
        self.tasks[0] = self.tasks.pop()
        self._heapify_down(0)
        
        return task
    
    def has_tasks(self):
        return bool(self.tasks)

# 使用示例
import time

scheduler = TaskScheduler()

# 添加一些任务
tasks = [
    Task(priority=1, data="低优先级任务1", timestamp=time.time()),
    Task(priority=3, data="高优先级任务1", timestamp=time.time()),
    Task(priority=2, data="中优先级任务1", timestamp=time.time()),
    Task(priority=3, data="高优先级任务2", timestamp=time.time()),
    Task(priority=1, data="低优先级任务2", timestamp=time.time())
]

for task in tasks:
    scheduler.add_task(task)

print("任务执行顺序:")
while scheduler.has_tasks():
    task = scheduler.get_next_task()
    print(f"执行任务: {task.data} (优先级: {task.priority})")
```

## 总结

堆排序是一种重要的排序算法，它的主要特点是：

1. 时间复杂度稳定在O(n log n)
2. 空间复杂度为O(1)
3. 不稳定排序
4. 适合大数据量排序

它在实际应用中的主要用途包括：
- 实现优先队列
- 处理大规模数据排序
- 任务调度系统
- Top-K问题

虽然在某些特定场景下可能不如其他排序算法，但堆排序的稳定的时间复杂度和低空间复杂度使其成为一个可靠的选择，特别是