前言
在面试中，经常会被问到topK问题，一般情况下都可以用堆来解决，但是如果没有自己写过堆的实现，可能经不住细问而面试失败（博主泪目T_T），所以专门写这篇文章介绍堆，争取做到量大量好还管饱。
堆的介绍
堆的数据结构
堆是一种特殊的树状数据结构，通常实现为一个数组，它具有以下主要性质：
-
堆属性：堆遵循一种特定的堆属性，这意味着堆中的每个节点都满足特定的比较关系。根据比较关系的不同，堆可以分为两种主要类型：
-
最大堆（Max Heap）：在最大堆中，对于每个节点
i，父节点的值始终大于或等于子节点的值。这意味着堆顶元素（根节点）是堆中的最大元素。最大堆一般用来堆排序，每次弹出堆的最大值。 -
最小堆（Min Heap）：在最小堆中，对于每个节点
i，父节点的值始终小于或等于子节点的值。这意味着堆顶元素是堆中的最小元素。最小堆一般用来解决topK问题，堆只保存最大的 K 个元素。
-
-
完全二叉树结构：堆通常以数组的形式实现，它是一种完全二叉树，也就是说，除了最后一层的节点，所有其他层都是满的。最后一层的节点尽量从左向右填充。这种结构有助于堆的高效实现。
-
父子节点关系：在堆中，父节点和子节点之间存在一种明确的关系。对于节点
i，其左子节点通常位于位置2 * i，右子节点位于位置2 * i + 1。反之，对于一个子节点j，其父节点位于位置j / 2。
堆的维护算法
堆是一种特殊的树状数据结构，而堆的维护算法是用于保持堆属性的关键操作。这些操作包括向上堆化（Heapify Up）和向下堆化（Heapify Down），它们确保堆在插入、删除或替换元素后仍然保持其特定属性，如最大堆或最小堆。
向上堆化（Heapify Up）
向上堆化是一种操作，通常用于在向堆中插入新元素后维持堆属性。下面是向上堆化的步骤：
-
比较新插入的元素与其父节点的值，根据堆的类型执行不同的操作。
-
如果是最大堆，新元素的值应该大于其父节点的值，如果不是，则交换它们。
-
如果是最小堆，新元素的值应该小于其父节点的值，如果不是，则交换它们。
-
重复上述比较和交换步骤，直到新元素在堆中找到了适当的位置，或者它成为堆的根节点。
向下堆化（Heapify Down）
向下堆化是一种操作，通常用于维持堆属性，当堆的根节点被删除或替换时。以下是向下堆化的步骤：
-
从根节点开始，比较根节点与其子节点中较大（或较小，根据堆类型）的节点。
-
如果根节点不是最大（或最小）的节点，与较大（或较小）的子节点交换。
-
重复上述比较和交换步骤，直到根节点满足堆属性，并且所有子树也是堆。
弹出堆顶最大值
在堆数据结构中，弹出堆顶最大值是一项常见的操作，特别是在最大堆（Max Heap）中。最大堆的特性是每个节点的值都大于或等于其子节点的值，因此堆顶元素是堆中的最大值。
以下是弹出堆顶最大值的操作步骤：
-
最大堆的堆顶元素即为堆中的最大值，通常是根节点的值。
-
要移除堆顶元素，将堆顶元素与堆中的最后一个元素交换。
-
移除交换后的堆顶元素，这相当于将最大值从堆中取出。
-
现在，堆可能不再满足最大堆的性质，需要进行向下堆化（Heapify Down）操作，以确保堆属性继续成立。
-
向下堆化的步骤是从根节点开始，比较根节点与其子节点中较大的节点（如果存在）。
-
如果根节点不是最大的，与较大的子节点交换，然后重复比较和交换步骤，直到根节点满足最大堆属性，并且所有子树也是最大堆。
堆的代码实现
大顶堆
大顶堆可以用来做堆排序，但是
package main
import "fmt"
type MaxHeap struct {
arr []int
}
func NewMaxHeap() *MaxHeap {
return &MaxHeap{}
}
// 入堆
func (h *MaxHeap) Push(x int) {
h.arr = append(h.arr, x)
h.up(len(h.arr) - 1)
}
// 这是用于插入元素到堆中的操作。
// 当向堆中插入一个元素时，它被添加到堆的末尾，然后通过向上堆化的过程，将它移到合适的位置，以满足最大堆性质。
// 这通常涉及与父节点比较并交换的过程，直到堆性质被恢复。
// 堆本来就是有序的，那么只需要将插入的元素，和父节点比较，然后交换就能保证堆的排序，类似冒泡一样
func (h *MaxHeap) up(index int) {
parent := (index - 1) / 2
if parent >= 0 && h.arr[index] > h.arr[parent] {
h.arr[index], h.arr[parent] = h.arr[parent], h.arr[index]
h.up(parent)
}
}
func (h *MaxHeap) Size() int {
return len(h.arr)
}
func (h *MaxHeap) IsEmpty() bool {
return h.Size() == 0
}
func (h *MaxHeap) PopMax() (int, bool) {
if h.IsEmpty() {
return 0, false
}
max := h.arr[0]
last := h.arr[len(h.arr)-1]
h.arr = h.arr[:len(h.arr)-1]
if !h.IsEmpty() {
h.arr[0] = last
h.down(0)
}
return max, true
}
//当把堆顶元素弹出时，需要重新维护堆
func (h *MaxHeap) down(index int) {
leftChild := 2*index + 1
rightChild := 2*index + 2
largest := index
if leftChild < h.Size() && h.arr[leftChild] > h.arr[largest] {
largest = leftChild
}
if rightChild < h.Size() && h.arr[rightChild] > h.arr[largest] {
largest = rightChild
}
if largest != index {
h.arr[index], h.arr[largest] = h.arr[largest], h.arr[index]
h.down(largest)
}
}
func heapSort(arrs []int) []int {
heap := NewMaxHeap()
// 插入元素到最大堆
for _, el := range arrs {
heap.Push(el)
}
max, ok := heap.PopMax()
i := 0
for ok {
max, ok = heap.PopMax()
arrs[i] = max
i++
}
return arrs
}
func main() {
heap := NewMaxHeap()
elements := []int{4, 10, 3, 5, 1}
fmt.Printf("排序后: %v \n", heapSort(elements))
// 插入元素到最大堆
for _, el := range elements {
heap.Push(el)
}
// 输出堆中的最大值
max, ok := heap.PopMax()
if ok {
fmt.Printf("最大值: %d\n", max)
}
// 输出剩余元素
fmt.Printf("剩余元素: %v\n", heap.arr)
}
小顶堆
小顶堆一般来说是不支持弹出最大元素的
type TopKHeap struct {
arr []int
size int
}
func NewTopKHeap(size int) *TopKHeap {
return &TopKHeap{
arr: make([]int, size),
size: 0,
}
}
func (t *TopKHeap) Push(val int) {
// 当堆未满时，需要插入元素到尾部，并且重新向上堆化
if t.size < len(t.arr) {
t.arr[t.size] = val
t.up(t.size)
t.size++
// 如果插入的元素比 最小值大，替换堆顶并向下堆化
} else if t.arr[0] < val {
t.arr[0] = val
t.down(0)
}
}
func (t *TopKHeap) up(index int) {
parent := (index - 1) / 2
for parent >= 0 && t.arr[parent] > t.arr[index] {
t.arr[parent], t.arr[index] = t.arr[index], t.arr[parent]
index = parent
parent = (index - 1) / 2
}
}
func (t *TopKHeap) down(index int) {
left := index*2 + 1
right := index*2 + 2
parent := index
if left < t.size && t.arr[left] < t.arr[parent] {
parent = left
}
if right < t.size && t.arr[right] < t.arr[parent] {
parent = right
}
if index != parent {
t.arr[index], t.arr[parent] = t.arr[parent], t.arr[index]
t.down(parent)
}
}
func main() {
heap := NewTopKHeap(5)
arrs := []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
for i := range arrs {
heap.Push(arrs[i])
}
fmt.Println(heap.arr)
}