堆

堆（Heap）是一种特殊的完全二叉树，所有的父节点都满足某种特定的顺序关系（大于或小于）与其子节点。堆通常有两种类型：最大堆和最小堆。在最大堆中，每个父节点的值都大于或等于其子节点的值；在最小堆中，每个父节点的值都小于或等于其子节点的值。

解决关于堆的算法题通常涉及以下几个操作：

建堆（Heapify）：将一个无序的数组构建成一个堆。对于最小堆，通常从最后一个非叶子节点开始向前调整，确保所有的父节点都小于其子节点。
插入（Insert）：向堆中插入一个新元素，然后上浮（或下沉）该元素，以保持堆的性质。
删除（Delete）：通常删除堆顶元素（最大堆中的最大元素或最小堆中的最小元素），然后将最后一个元素移动到堆顶，并进行下沉操作，以保持堆的性质。
堆排序（Heap Sort）：利用堆的性质进行排序。通过不断移除堆顶元素并重建堆来实现。
更新（Update）：更新堆中的某个元素，然后根据其值的增减进行上浮或下沉操作。

在 Go 语言中，可以使用container/heap包来实现堆的操作，但为了更好地理解堆的内部机制，我们可以手动实现堆的各种操作。下面是一个最小堆的 Go 语言实现示例：

package main

import (
	"fmt"
)

// MinHeap struct has a slice that holds the array
type MinHeap struct {
	array []int
}

// Insert adds an element to the heap
func (h *MinHeap) Insert(key int) {
	h.array = append(h.array, key)
	h.minHeapifyUp(len(h.array) - 1)
}

// Extract returns the smallest key, and removes it from the heap
func (h *MinHeap) Extract() (int, bool) {
	if len(h.array) == 0 {
		return 0, false
	}

	min := h.array[0]
	lastIndex := len(h.array) - 1
	// Move the last element to the top
	h.array[0] = h.array[lastIndex]
	h.array = h.array[:lastIndex]

	h.minHeapifyDown(0)

	return min, true
}

// minHeapifyUp will heapify from bottom top
func (h *MinHeap) minHeapifyUp(index int) {
	for h.array[parent(index)] > h.array[index] {
		h.swap(parent(index), index)
		index = parent(index)
	}
}

// minHeapifyDown will heapify from top bottom
func (h *MinHeap) minHeapifyDown(index int) {
	lastIndex := len(h.array) - 1
	l, r := left(index), right(index)
	childToCompare := 0

	for l <= lastIndex {
		if l == lastIndex { // when left child is the only child
			childToCompare = l
		} else if h.array[l] < h.array[r] { // when left child is smaller
			childToCompare = l
		} else { // when right child is smaller
			childToCompare = r
		}

		if h.array[index] > h.array[childToCompare] {
			h.swap(index, childToCompare)
			index = childToCompare
			l, r = left(index), right(index)
		} else {
			return
		}
	}
}

// get the parent index
func parent(i int) int {
	return (i - 1) / 2
}

// get the left child index
func left(i int) int {
	return 2*i + 1
}

// get the right child index
func right(i int) int {
	return 2*i + 2
}

// swap keys in the array
func (h *MinHeap) swap(i1, i2 int) {
	h.array[i1], h.array[i2] = h.array[i2], h.array[i1]
}

func main() {
	minHeap := &MinHeap{}
	fmt.Println("Min Heap")
	minHeap.Insert(10)
	minHeap.Insert(23)
	minHeap.Insert(36)
	minHeap.Insert(18)
	minHeap.Insert(2)
	minHeap.Insert(3)
	minHeap.Insert(41)

	fmt.Println("Extract min:", minHeap.Extract())
}

在这个例子中，我们定义了一个MinHeap结构体，它有一个array切片来存储堆中的元素。我们实现了Insert和Extract方法来添加和移除元素，以及minHeapifyUp和minHeapifyDown方法来维护堆的性质。parent、left和right函数用于计算父节点和子节点的索引。最后，swap方法用于交换元素。

当解决堆相关问题时，通常需要根据问题的具体要求来调整堆的实现细节，比如可能需要实现最大堆，或者需要在堆中存储复杂的数据结构等。理解堆的基本操作和性质是解决这些问题的关键。

在 C++中，堆通常可以通过标准库中的priority_queue来实现，它默认是一个最大堆。如果你想实现一个最小堆，你可以通过传递一个比较函数来改变排序的顺序。下面是一些使用 C++标准库中的priority_queue来解决堆相关问题的例子。

最大堆的例子

#include <iostream>
#include <queue>

int main() {
    // 默认是最大堆
    std::priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(30);
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);

    // 删除并获取最大元素
    while (!maxHeap.empty()) {
        int maxElement = maxHeap.top(); // 获取最大元素
        std::cout << maxElement << " ";
        maxHeap.pop(); // 移除最大元素
    }

    return 0;
}

最小堆的例子

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

int main() {
    // 使用greater<>来创建最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // 插入元素
    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);

    // 删除并获取最小元素
    while (!minHeap.empty()) {
        int minElement = minHeap.top(); // 获取最小元素
        std::cout << minElement << " ";
        minHeap.pop(); // 移除最小元素
    }

    return 0;
}

如果你需要手动实现一个堆，而不是使用priority_queue，你可以使用一个动态数组（如std::vector）来存储堆的元素，并实现堆的各种操作。下面是一个手动实现的最小堆：

#include <iostream>
#include <vector>

class MinHeap {
private:
    std::vector<int> data;

    void heapifyUp(int index) {
        while (index > 0 && data[parent(index)] > data[index]) {
            std::swap(data[parent(index)], data[index]);
            index = parent(index);
        }
    }

    void heapifyDown(int index) {
        int lastIndex = data.size() - 1;
        int leftChild, rightChild, minIndex;

        while (left(index) <= lastIndex) {
            leftChild = left(index);
            rightChild = right(index);
            minIndex = index;

            if (data[minIndex] > data[leftChild]) {
                minIndex = leftChild;
            }

            if (rightChild <= lastIndex && data[minIndex] > data[rightChild]) {
                minIndex = rightChild;
            }

            if (minIndex != index) {
                std::swap(data[index], data[minIndex]);
                index = minIndex;
            } else {
                break;
            }
        }
    }

    int left(int parent) {
        return 2 * parent + 1;
    }

    int right(int parent) {
        return 2 * parent + 2;
    }

    int parent(int child) {
        return (child - 1) / 2;
    }

public:
    void insert(int key) {
        data.push_back(key);
        heapifyUp(data.size() - 1);
    }

    int getMin() {
        return data.front();
    }

    void removeMin() {
        if (data.size() == 0) {
            throw std::out_of_range("Heap is empty");
        }
        data[0] = data.back();
        data.pop_back();
        heapifyDown(0);
    }
};

int main() {
    MinHeap minHeap;
    minHeap.insert(3);
    minHeap.insert(2);
    minHeap.insert(15);
    minHeap.insert(5);
    minHeap.insert(4);
    minHeap.insert(45);

    std::cout << "Min value: " << minHeap.getMin() << std::endl;

    minHeap.removeMin();
    std::cout << "Min value: " << minHeap.getMin() << std::endl;

    return 0;
}

在这个例子中，我们定义了一个MinHeap类，它有一个私有的std::vector<int>来存储堆中的元素。我们实现了insert和removeMin方法来添加和移除元素，以及heapifyUp和heapifyDown方法来维护堆的性质。left、right和parent函数用于计算父节点和子节点的索引。

hot-100

堆

最大堆的例子

最小堆的例子