排序算法-堆排序-EW帮帮网

算法排序-堆排序

简介

堆排序（Heap Sort）是利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

堆排序由J. W. J. Williams在1964年发明，是一种选择排序的改进版本。它的时间复杂度为O(n log n)，且是原地排序算法。

算法原理

堆排序的基本思想是：

构建最大堆: 将待排序数组构造成一个最大堆
交换和调整: 将堆顶元素（最大值）与末尾元素交换，然后调整剩余元素重新构成最大堆
重复过程: 重复步骤2，直到所有元素都被排序

堆的性质

最大堆: 父节点的值大于或等于子节点的值
最小堆: 父节点的值小于或等于子节点的值
完全二叉树: 除了最后一层，其他层都是满的，最后一层从左到右填充

Go语言实现

基础版本

package main

import "fmt"

// HeapSort 堆排序主函数
func HeapSort(arr []int) {
    n := len(arr)
    
    // 构建最大堆（从最后一个非叶子节点开始）
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    
    // 一个个从堆顶取出元素
    for i := n - 1; i > 0; i-- {
        // 将当前最大元素移到数组末尾
        arr[0], arr[i] = arr[i], arr[0]
        
        // 调整剩余元素重新构成最大堆
        heapify(arr, i, 0)
    }
}

// heapify 调整堆，使其满足最大堆性质
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)
    }
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("排序前:", arr)
    
    HeapSort(arr)
    fmt.Println("排序后:", arr)
}

带步骤显示的版本

package main

import "fmt"

var step int

// HeapSortWithSteps 带步骤显示的堆排序
func HeapSortWithSteps(arr []int) {
    n := len(arr)
    step = 0
    
    fmt.Printf("初始数组: %v\n", arr)
    fmt.Println("\n=== 构建最大堆阶段 ===")
    
    // 构建最大堆
    for i := n/2 - 1; i >= 0; i-- {
        step++
        fmt.Printf("步骤 %d: 调整节点 %d\n", step, i)
        heapifyWithSteps(arr, n, i, "构建")
        fmt.Printf("当前状态: %v\n", arr)
        printHeapStructure(arr, n)
        fmt.Println()
    }
    
    fmt.Println("=== 排序阶段 ===")
    
    // 排序过程
    for i := n - 1; i > 0; i-- {
        step++
        fmt.Printf("步骤 %d: 交换堆顶 %d 和末尾元素 %d\n", 
                   step, arr[0], arr[i])
        
        // 交换堆顶和末尾元素
        arr[0], arr[i] = arr[i], arr[0]
        fmt.Printf("交换后: %v\n", arr)
        
        // 调整剩余元素
        fmt.Printf("调整前 %d 个元素重新构成最大堆:\n", i)
        heapifyWithSteps(arr, i, 0, "排序")
        fmt.Printf("调整后: %v\n", arr)
        printHeapStructure(arr, i)
        fmt.Println()
    }
}

// heapifyWithSteps 带步骤显示的堆调整
func heapifyWithSteps(arr []int, n, i int, phase string) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2
    
    fmt.Printf("  检查节点 %d (值: %d)", i, arr[i])
    if left < n {
        fmt.Printf(", 左子节点 %d (值: %d)", left, arr[left])
    }
    if right < n {
        fmt.Printf(", 右子节点 %d (值: %d)", right, arr[right])
    }
    fmt.Println()
    
    // 找到最大值
    if left < n && arr[left] > arr[largest] {
        largest = left
        fmt.Printf("  左子节点 %d 更大\n", left)
    }
    
    if right < n && arr[right] > arr[largest] {
        largest = right
        fmt.Printf("  右子节点 %d 更大\n", right)
    }
    
    // 如果需要交换
    if largest != i {
        fmt.Printf("  交换节点 %d (值: %d) 和节点 %d (值: %d)\n", 
                   i, arr[i], largest, arr[largest])
        arr[i], arr[largest] = arr[largest], arr[i]
        
        // 递归调整
        heapifyWithSteps(arr, n, largest, phase)
    } else {
        fmt.Printf("  节点 %d 已满足堆性质\n", i)
    }
}

// printHeapStructure 打印堆的树形结构
func printHeapStructure(arr []int, n int) {
    if n == 0 {
        return
    }
    
    fmt.Println("堆的树形结构:")
    printHeapLevel(arr, n, 0, 0)
}

func printHeapLevel(arr []int, n, index, level int) {
    if index >= n {
        return
    }
    
    // 打印右子树
    printHeapLevel(arr, n, 2*index+2, level+1)
    
    // 打印当前节点
    for i := 0; i < level; i++ {
        fmt.Print("    ")
    }
    fmt.Printf("%d\n", arr[index])
    
    // 打印左子树
    printHeapLevel(arr, n, 2*index+1, level+1)
}

堆数据结构实现

package main

import "fmt"

// MaxHeap 最大堆结构
type MaxHeap struct {
    data []int
}

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

// Insert 插入元素
func (h *MaxHeap) Insert(val int) {
    h.data = append(h.data, val)
    h.heapifyUp(len(h.data) - 1)
}

// ExtractMax 提取最大元素
func (h *MaxHeap) ExtractMax() (int, bool) {
    if len(h.data) == 0 {
        return 0, false
    }
    
    max := h.data[0]
    lastIndex := len(h.data) - 1
    
    // 将最后一个元素移到根部
    h.data[0] = h.data[lastIndex]
    h.data = h.data[:lastIndex]
    
    // 向下调整
    if len(h.data) > 0 {
        h.heapifyDown(0)
    }
    
    return max, true
}

// heapifyUp 向上调整
func (h *MaxHeap) heapifyUp(index int) {
    for index > 0 {
        parentIndex := (index - 1) / 2
        if h.data[index] <= h.data[parentIndex] {
            break
        }
        h.data[index], h.data[parentIndex] = h.data[parentIndex], h.data[index]
        index = parentIndex
    }
}

// heapifyDown 向下调整
func (h *MaxHeap) heapifyDown(index int) {
    for {
        largest := index
        leftChild := 2*index + 1
        rightChild := 2*index + 2
        
        if leftChild < len(h.data) && h.data[leftChild] > h.data[largest] {
            largest = leftChild
        }
        
        if rightChild < len(h.data) && h.data[rightChild] > h.data[largest] {
            largest = rightChild
        }
        
        if largest == index {
            break
        }
        
        h.data[index], h.data[largest] = h.data[largest], h.data[index]
        index = largest
    }
}

// Size 返回堆大小
func (h *MaxHeap) Size() int {
    return len(h.data)
}

// Peek 查看最大元素
func (h *MaxHeap) Peek() (int, bool) {
    if len(h.data) == 0 {
        return 0, false
    }
    return h.data[0], true
}

// HeapSortUsingHeap 使用堆数据结构进行排序
func HeapSortUsingHeap(arr []int) []int {
    heap := NewMaxHeap()
    
    // 将所有元素插入堆
    for _, val := range arr {
        heap.Insert(val)
    }
    
    // 从堆中依次提取最大元素
    result := make([]int, len(arr))
    for i := len(arr) - 1; i >= 0; i-- {
        max, _ := heap.ExtractMax()
        result[i] = max
    }
    
    return result
}

func main() {
    // 测试基础堆排序
    arr1 := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("=== 基础堆排序 ===")
    fmt.Println("排序前:", arr1)
    HeapSort(arr1)
    fmt.Println("排序后:", arr1)
    
    // 测试带步骤显示的堆排序
    arr2 := []int{4, 10, 3, 5, 1}
    fmt.Println("\n=== 带步骤显示的堆排序 ===")
    HeapSortWithSteps(arr2)
    
    // 测试使用堆数据结构的排序
    arr3 := []int{5, 2, 8, 1, 9, 3}
    fmt.Println("\n=== 使用堆数据结构的排序 ===")
    fmt.Println("排序前:", arr3)
    sorted := HeapSortUsingHeap(arr3)
    fmt.Println("排序后:", sorted)
}

复杂度分析

时间复杂度

构建堆: O(n) - 虽然看起来是O(n log n)，但实际分析为O(n)
排序过程: O(n log n) - n次提取操作，每次O(log n)
总体: O(n log n) - 所有情况下都是O(n log n)

空间复杂度

空间复杂度: O(1) - 原地排序，只需要常数级别的额外空间

算法特点

优点

时间复杂度稳定: 始终为O(n log n)
原地排序: 只需要O(1)的额外空间
不依赖输入: 性能不受输入数据分布影响
实现相对简单: 比快速排序更容易实现

缺点

不稳定: 相等元素的相对位置可能改变
缓存性能差: 堆操作的内存访问模式对缓存不友好
实际性能: 虽然理论复杂度好，但实际运行时间通常比快速排序慢

堆的应用

1. 优先队列

// PriorityQueue 优先队列实现
type PriorityQueue struct {
    heap *MaxHeap
}

func NewPriorityQueue() *PriorityQueue {
    return &PriorityQueue{
        heap: NewMaxHeap(),
    }
}

func (pq *PriorityQueue) Enqueue(val int) {
    pq.heap.Insert(val)
}

func (pq *PriorityQueue) Dequeue() (int, bool) {
    return pq.heap.ExtractMax()
}

2. Top K 问题

// FindTopK 找到数组中最大的K个元素
func FindTopK(arr []int, k int) []int {
    heap := NewMaxHeap()
    
    for _, val := range arr {
        heap.Insert(val)
    }
    
    result := make([]int, 0, k)
    for i := 0; i < k && heap.Size() > 0; i++ {
        max, _ := heap.ExtractMax()
        result = append(result, max)
    }
    
    return result
}

实际应用场景

堆排序广泛应用于：

系统调度: 操作系统的进程调度
优先队列: 任务优先级管理
图算法: Dijkstra算法、Prim算法等
数据流处理: 实时数据的Top K问题
内存管理: 堆内存分配算法
事件驱动系统: 事件优先级处理

性能测试

package main

import (
    "fmt"
    "math/rand"
    "time"
)

// 性能测试函数
func benchmarkHeapSort(size int) {
    // 生成随机数组
    arr := make([]int, size)
    for i := 0; i < size; i++ {
        arr[i] = rand.Intn(10000)
    }
    
    start := time.Now()
    HeapSort(arr)
    duration := time.Since(start)
    
    fmt.Printf("数组大小: %d, 排序时间: %v\n", size, duration)
}

// 比较不同输入情况下的性能
func compareHeapSortPerformance() {
    size := 10000
    
    // 随机数组
    randomArr := make([]int, size)
    for i := 0; i < size; i++ {
        randomArr[i] = rand.Intn(10000)
    }
    
    // 已排序数组
    sortedArr := make([]int, size)
    for i := 0; i < size; i++ {
        sortedArr[i] = i
    }
    
    // 逆序数组
    reverseArr := make([]int, size)
    for i := 0; i < size; i++ {
        reverseArr[i] = size - i
    }
    
    // 测试随机数组
    start := time.Now()
    HeapSort(randomArr)
    fmt.Printf("随机数组排序时间: %v\n", time.Since(start))
    
    // 测试已排序数组
    start = time.Now()
    HeapSort(sortedArr)
    fmt.Printf("已排序数组排序时间: %v\n", time.Since(start))
    
    // 测试逆序数组
    start = time.Now()
    HeapSort(reverseArr)
    fmt.Printf("逆序数组排序时间: %v\n", time.Since(start))
}

func main() {
    fmt.Println("=== 堆排序性能测试 ===")
    sizes := []int{1000, 10000, 100000, 1000000}
    
    for _, size := range sizes {
        benchmarkHeapSort(size)
    }
    
    fmt.Println("\n=== 不同输入情况性能比较 ===")
    compareHeapSortPerformance()
}

总结

堆排序是一个重要的排序算法，它结合了堆数据结构的特性，提供了稳定的O(n log n)时间复杂度和O(1)空间复杂度。虽然在实际应用中可能不如快速排序常用，但其稳定的性能特征使其在某些特定场景中非常有价值。

关键要点:

基于堆数据结构，利用完全二叉树的性质
时间复杂度稳定为O(n log n)，空间复杂度为O(1)
是原地排序算法，但不稳定
适合需要稳定性能的场景
堆数据结构在优先队列等应用中非常重要

排序算法-堆排序