堆结构介绍

堆

目录

• 堆
  • 数据结构概述
  • 数据结构适用条件
  • 算法实现
    • 最大堆的基本操作
    • 最大堆排序
  • LeetCode 题目

数据结构概述

• 堆一般使用二叉树来表示，堆是一棵完全二叉树。
• 堆有两种类型：最大堆和最小堆。最大堆：每个节点的值都大于或等于其左右子节点的值。最小堆：每个节点的值都小于或等于其左右子节点的值。
• 堆能够快速的获取最大值或最小值。

数据结构适用条件

• 主要是用实现优先队列。
• 可以用来实现排序。

算法实现

最大堆的基本操作

package main

type MaxHeap struct {
    data []int // 存储堆元素的切片
}

// NewMaxHeap 创建一个新的最大堆，并对初始元素进行堆化
func NewMaxHeap(elem []int) *MaxHeap {
    n := len(elem)
    // 避免直接修改传入的切片，因为切片可能会在外部被修改
    data := make([]int, n)
    copy(data, elem)

    maxHeap := &MaxHeap{
        data: data,
    }

    // 从最后一个非叶子节点开始，依次向上进行下沉操作，构建最大堆
    for i := parent(n - 1); i >= 0; i-- {
        maxHeap.siftDown(i)
    }
    return maxHeap
}

// IsEmpty 判断堆是否为空
func (h *MaxHeap) IsEmpty() bool {
    return len(h.data) == 0
}

// Size 返回堆中元素的数量
func (h *MaxHeap) Size() int {
    return len(h.data)
}

// parent 返回父节点的索引
func parent(index int) int {
    return (index - 1) / 2
}

// leftChild 返回左子节点的索引
func leftChild(index int) int {
    return 2*index + 1
}

// rightChild 返回右子节点的索引
func rightChild(index int) int {
    return 2*index + 2
}

// Add 向堆中添加一个元素，并保持堆的性质
func (h *MaxHeap) Add(e int) {
    h.data = append(h.data, e)
    h.siftUp(len(h.data) - 1) // 将新添加的元素上浮到正确的位置
}

// siftUp 上浮操作，将索引为 k 的元素上移以维持堆的性质
func (h *MaxHeap) siftUp(k int) {
    for k > 0 && h.data[parent(k)] < h.data[k] {
        // 如果当前节点大于其父节点，交换它们的值
        h.data[parent(k)], h.data[k] = h.data[k], h.data[parent(k)]
        k = parent(k) // 继续向上比较
    }
}

// FindMax 返回堆中的最大元素（即堆顶元素）
func (h *MaxHeap) FindMax() int {
    if h.IsEmpty() {
        panic("Cannot FindMax when heap is empty.")
    }
    return h.data[0]
}

// ExtractMax 取出并返回堆中的最大元素，然后重新调整堆
func (h *MaxHeap) ExtractMax() int {
    max := h.FindMax() // 堆顶元素即为最大值
    n := len(h.data) - 1
    h.data[0] = h.data[n]     // 将最后一个元素移动到堆顶
    h.data = h.data[:n]       // 删除最后一个元素
    h.siftDown(0)             // 从堆顶开始下沉，恢复堆的性质
    return max
}

// siftDown 下沉操作，将索引为 k 的元素下移以维持堆的性质
func (h *MaxHeap) siftDown(k int) {
    n := len(h.data)
    for leftChild(k) < n {
        j := leftChild(k) // 左子节点索引
        // 如果右子节点存在且大于左子节点，则用右子节点进行比较
        if j+1 < n && h.data[j+1] > h.data[j] {
            j = rightChild(k)
        }

        // 如果当前节点大于等于子节点中最大的，堆性质已满足，退出循环
        if h.data[k] >= h.data[j] {
            break
        }
        // 否则，交换当前节点与子节点中较大的一个
        h.data[k], h.data[j] = h.data[j], h.data[k]
        k = j // 继续向下比较
    }
}

最大堆排序

package main

import "fmt"

type MaxHeap struct {
    data []int
}

// Heapify 建立最大堆
func Heapify(arr []int) {
    n := len(arr)
    // 从最后一个非叶子节点开始，依次执行下沉操作
    for i := parent(n - 1); i >= 0; i-- {
        siftDown(arr, n, i)
    }
}

// parent 返回父节点的索引
func parent(index int) int {
    return (index - 1) / 2
}

// leftChild 返回左子节点的索引
func leftChild(index int) int {
    return 2*index + 1
}

// rightChild 返回右子节点的索引
func rightChild(index int) int {
    return 2*index + 2
}

// siftDown 对节点进行下沉操作，维持堆的性质
func siftDown(arr []int, n, k int) {
    for leftChild(k) < n {
        j := leftChild(k)
        // 如果右子节点存在且大于左子节点，使用右子节点
        if j+1 < n && arr[j+1] > arr[j] {
            j = rightChild(k)
        }
        // 如果当前节点大于等于子节点中最大的，结束循环
        if arr[k] >= arr[j] {
            break
        }
        // 交换当前节点与子节点中较大的一个
        arr[k], arr[j] = arr[j], arr[k]
        // 继续向下比较
        k = j
    }
}

// HeapSort 原地堆排序算法
func HeapSort(arr []int) {
    n := len(arr)
    // 建立最大堆
    Heapify(arr)
    // 依次取出堆顶元素（最大值）到数组末尾
    for i := n - 1; i > 0; i-- {
        // 将堆顶元素与当前堆的最后一个元素交换
        arr[0], arr[i] = arr[i], arr[0]
        // 调整堆，使其满足最大堆性质
        siftDown(arr, i, 0) // 注意，此时堆的大小为 i
    }
}

func main() {
    arr := []int{3, 5, 1, 10, 2, 7}
    HeapSort(arr)
    fmt.Println(arr) // 输出: [1 2 3 5 7 10]
}

LeetCode 题目

• 215. 数组中的第K个最大元素