chapter_heap/heap/

[giscus[bot]]

chapter_heap/heap/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_heap/heap/

[hello-ikun]

这部分的py我先预定一下。今晚回去更一下

[krahets]

好，冲！

[neonhanako]

"输入数据并建堆"小节中提到“元素入堆的时间复杂度为O(n)”，这里应该是O(logn)吧，“元素入堆”那一小节也提到了这一点（ps.很感谢k神的教程，一路看下来帮助很大（刚刚回复到别人的评论上了不好意思orz

[krahets]

原文是正确的～

• 元素入堆是对单个元素的操作，时间复杂度是 $O(\log n)$ ；
• 建堆是一次性输入 $n$ 个元素，如果用元素入堆来实现是 $O(n \log n)$ ，但可以被优化到 $O(n)$ ；

谢谢鼓励哇，一起加油

[Github-632]

歪个楼，想请问下堆顶元素出堆的poll（）用的是单词的哪个含义呀，有无英语好的大佬解答一下呢。是poll的头顶，顶部；还是轮询，查询

[Github-632]

poll还有“截掉（动物，尤指小牛）的角“的意思，感觉这个最形象！

[krahets]

Hi，这里沿用了 Java 中的 poll() ，与之对应的操作是 offer() ～

[PPcattt]

heap.java 堆顶元素出堆好像没有名为heap的堆

[PPcattt]

说的是采用数组存储堆，而实际确实使用列表来实现堆

[krahets]

emmm 这里我们没有特意区分动态数组和数组。使用动态数组是为了方便扩容。

[fallenleavesguy]

请问一下，堆排序怎么样的，能不能补充一下呢。二叉搜索树排序能明白，但是堆 “依次将所有元素弹出”也不是有序的啊，只是上面的比下面的大，下面的还是保证不了顺序的。能简单说一下吗？谢谢大佬

[krahets]

哈喽，这里的“弹出”是指元素出堆。每次出堆时，堆都会进行相应调整，保持根节点最小（或最大）。

堆排序会加在排序算法章。

[fallenleavesguy]

请问一下，这里的“堆”与程序语言中的在堆中为对象分配内存，是同一个东西吗？

[krahets]

好问题～两者不是同一个东西，只是碰巧都叫"堆"。

计算机系统内存中的"堆"是动态内存分配的一部分，程序在运行时可以使用它来存储数据。程序可以请求一定量的堆内存，用于存储如对象和数组等复杂结构。当这些数据不再需要时，程序需要释放这些内存，以防止内存泄露。相较于栈内存，堆内存的管理和使用需要更谨慎，不恰当的使用可能会导致内存泄露和野指针等问题。

[mech-jiangyuxu]

k神，堆初始化的时候，这一段代码没搞明白，
def init(self, nums: list[int]):
self.max_heap = nums
for i in range(self.parent(self.size() - 1), -1, -1):
self.sift_down(i)
我理解为直接从堆顶往堆底比较就可以了，为啥不是以下这种方式呢？
def init(self, nums: list[int]):
self.max_heap = nums
self.sift_down(0)

[mech-jiangyuxu]

这个排版怎么自己乱了。

[krahets]

这里是建堆操作，下一节有讲哦

[zhuasdfg]

k神，代码里的注释能不能写的更详细一点，特别是这几节我每次看代码都要理解好久，// 当“越过根节点”或“节点无需修复”时，结束堆化if (p < 0 || maxHeap.get(i) <= maxHeap.get(p))，就像这里p<0，我想了好一会才理解它是根据parent()表示的越过根节点。

[krahets]

好的，不过写太详细代码也会变冗长。每当遇到“想很久才明白”的情况，往往也是变强的时刻

[cylovecode]

siftUp(size() - 1); k神，这里的size(),不用写成maxHeap.size()吗？

[cylovecode]

int size = maxHeap.size(); 不好意思没有看到前面的定义，不过我有点疑惑这个为啥定义了用的时候还要带个括号

[krahets]

请区分变量和方法，size() 是调用方法，size 是访问变量

[luommy]

不错，感觉可以和cookbook一起看，labuladong的感觉不适合算法新手完全看不进去

[malone6]

哪个cookbook？

[luommy]

halfrost，go版本的那个

[sdz123]

堆顶元素出堆 为什么选择操作交换堆顶和最右子节点而不是交换堆顶和最底层最左子节点呢？

[krahets]

在二叉树的数组表示中，最右下角的子节点对应数组的最后一个元素，这样弹出操作是安全的。

如果和最左下角的元素交换，然后将交换后的最左下角的元素弹出，则该元素后面的元素都会发生“位移”，相当于将二叉树部分的底层节点左移了。这样有可能会破坏堆的性质，是有问题的。

[sdz123]

感谢您的回复，豁然开朗。

[Tinywan]

为何没有PHP?

[krahets]

因为你没有来贡献 🤣

[2000cris7]

哈哈哈哈哈

[KLM1109]

my_heap.cpp多了行注释// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出

[krahets]

谢谢！

[topul]

不错，跟《Java编程的逻辑》一起看，看看Java的实现，看看大佬的实现，加强印象

[nlsxsy]

元素入堆那里，高度为什么要加上时间复杂度啊

[fishmans06]

您这回复效率，实在令人佩服……

[2000cris7]

哈哈哈哈

[owenwu95]

請問 C 的索引映射公式函數是不是多了MaxHeap *maxHeap的無用參數？

[xiaozhengF]

感觉只需要一个index就行了

[selfboot]

搞了个动态可视化来解释堆的操作，可以看 https://gallery.selfboot.cn/algorithms/heap/

[jerryhanjj]

很不错～

[HsCodeLab]

k神,我想问一下你这个动画图片是怎么生成的,用的什么软件吗?我在想一种可能,如果各种排序,各种递归之类的都有相应的动画图解,那理解起来就简单多了,也不需要自己手动画图,所以k神,这是啥软件或者什么技术手段,我也想研究一下,便于我理解别的知识点,免去手动画图的步骤.谢谢!

[selfboot]

我最近在做这个： https://gallery.selfboot.cn/algorithms/
就是各种算法的web可视化，用 gpt4和claude3.5 辅助，感觉还不错。
比如 链表 https://gallery.selfboot.cn/algorithms/linkedlist/
前缀树 https://gallery.selfboot.cn/algorithms/trie/

[1159249257]

堆默认是最常使用的二叉堆，而二叉堆只是优先队列的一种是实现方式

[Than-Sing]

NOTE：用while True可以避免sift_down和sift_up的递归，直接换掉下个i即可

[LiHuigui]

想了一下，其实这里提供的方法也完全能删除任意一个节点对吧？也是把要删除的节点和堆底元素（最右叶节点）交换后删除，然后从这个换过来的节点开始进行堆化。甚至代码都不用改，只要更改传进去的swap和siftdown函数的节点索引就行。（我知道删除根节点的带来的意义重大，删除任意节点没什么意义，就是单纯思考了一下这个问题）

[LiHuigui]

不对，如果是删除叶子节点的话以上逻辑就不对了，而且似乎变得很难处理，有时候叶子节点甚至是无法删除的。我能想象一个无法删除叶子节点的大顶堆的例子:[10,2,9,1,2,7,8]，在这个例子中叶子节点1是无法被删除的。删除了必定会导致二叉树不再是完全二叉树。

[kingleonardo999]

我觉得你一开始的想法是对的，只需要与最后一个叶节点交换，再进行向上和向下的堆化（应该是都要指执行的），理论上可以删除任意节点吧，只是删除根节点，没有了向上堆化的这一过程

[WJZL0]

作者你好，堆的初始化结构没写，我根据后面的结构，补充了一下C语言版本的MaxHeap的结构
typedef struct MaxHeap {
int size;
int *data;
} MaxHeap;

[WJZL0]

我有补充了一点，应该定义一个实现堆的函数，创建堆
完整代码：
// 最大堆的实现
typedef struct {
int size;
int *data;
int capacity;
} MaxHeap;

//创建一个堆，容量为capacity
MaxHeap createMaxHeap(int capacity)
{
MaxHeap maxHeap = (MaxHeap)malloc(sizeof(MaxHeap));
maxHeap->size = 0;
maxHeap->capacity = capacity;
maxHeap->data = (int)malloc(sizeof(int)*capacity);
return maxHeap;
}

[krahets]

Hi，请前往代码仓库下载代码（ https://github.com/krahets/hello-algo ），可一键运行

[ChineseCz]

if (p < 0 || maxHeap.get(i) <= maxHeap.get(p))
作者这里，i最小为0，p=(i-1)/2，最小也是0.
这里p<0是多余的
或 后的部分包括了 根节点溢出的情况

[daichang01]

我将最小堆的实现封装为了一个类
#include
#include
#include

using namespace std;

class MinHeap {
public:
int left(int i);
int right(int i);
int parent(int i);
int peek();
int size();
void push(int i);
void pop();
bool isEmpty();
void printMinHeap();
private:
vector minHeap;

};

bool MinHeap::isEmpty() {
return minHeap.empty();
}
int MinHeap::left(int i) {
return 2* i+ 1;
}

int MinHeap::right(int i) {
return 2*i + 2;
}

int MinHeap::parent(int i) {
return (i - 1) / 2;
}

int MinHeap::peek() {
if (isEmpty()) {
throw out_of_range("尝试访问空堆");
}
return minHeap[0];
}

int MinHeap::size() {
return minHeap.size();
}

void MinHeap::push(int i) {
minHeap.push_back(i);
int index = size() - 1;
while(true) {
//获取节点index的父节点
int p = parent(index);
//当越过根节点 或节点无需交换时，结束堆化
if (p < 0 || minHeap[index] >= minHeap[p]) {
break;
}
swap(minHeap[index], minHeap[p]);
//循环向上堆化
index = p;
}

}

void MinHeap::pop() {
if (isEmpty()) {
throw out_of_range("堆为空");
}
//交换根节点与最右叶节点(交换首元素和尾元素)
swap(minHeap[0], minHeap[size() - 1]);
//删除节点
minHeap.pop_back();
int index = 0;
//从顶至底堆化
while (true) {
// 判断节点 index, l, r 中值最小的节点，记为 min_index
int l = left(index), r = right(index), min_index = index;
if (l < size() && minHeap[l] < minHeap[min_index])
min_index = l;
if (r < size() && minHeap[r] < minHeap[min_index])
min_index = r;
//如果节点index最小，无需继续堆化
if (min_index == index)
break;
swap(minHeap[index], minHeap[min_index]);
index = min_index;

}

}

void MinHeap::printMinHeap() {
cout << "minHeap:";
for (int num: minHeap) {
cout << num << " ";
}
cout << endl;
}

int main() {
vector input = {2,1,4,5,6,3};
MinHeap minheap;
for (int i: input) {
minheap.push(i);
}
cout << "min val = " << minheap.peek() << endl;
minheap.printMinHeap();
minheap.pop();
cout << "min val = " << minheap.peek() << endl;
minheap.pop();
cout << "min val = " << minheap.peek() << endl;
minheap.pop();
cout << "min val = " << minheap.peek() << endl;
minheap.pop();
cout << "min val = " << minheap.peek() << endl;
minheap.pop();
cout << "min val = " << minheap.peek() << endl;
// minheap.pop();
// cout << "min val = " << minheap.peek() << endl;

return 0;

}

[tstanon]

小顶堆的实现，只需要修改Heaptify的向上和向下过程即可。
c代码如下：

// 小顶堆: 对 heaptifyUp 和 heaptifyDown 函数的逻辑进行一些调整。
void initHeap(float **arr, int *size) { *arr = (float *)malloc(sizeof(float) * MAX_SIZE); *size = 0; }
void peekTop(float *arr, int size, float *x) { if (size <= 0) return; *x = arr[0]; }
void getParent(int i, int *p_idx) { *p_idx = (i - 1) / 2; }
void getLeftChild(int i, int *lc_idx) { *lc_idx = 2 * i + 1; }
void getRightChild(int i, int *rc_idx) { *rc_idx = 2 * i + 2; }
void heaptifyUp(float *arr, int idx) { // 比较当前节点与其父节点的大小。如果当前节点的值小于父节点的值，则交换它们，并继续向上调整。
    int cur = idx;
    while (cur > 0) {  // 只要 cur 不是根节点
        int par; getParent(cur, &par); if (arr[cur] >= arr[par]) break; // 如果当前节点大于等于父节点，退出循环
        float tmp = arr[cur]; arr[cur] = arr[par]; arr[par] = tmp; cur = par;  // 交换当前节点和父节点, 更新 cur 为父节点索引
    }
}
void heaptifyDown(float *arr, int size, int idx) { // 比较当前节点与其左右子节点的大小。选择最小的子节点，如果当前节点大于这个子节点，则交换它们，并继续向下调整。
    int cur = idx;
    while (true) {
        int lc, rc, minidx = cur; getLeftChild(cur, &lc); getRightChild(cur, &rc);
        if (lc < size && arr[lc] < arr[minidx]) { minidx = lc; } // 找到当前节点和左子节点中的最小值
        if (rc < size && arr[rc] < arr[minidx]) { minidx = rc; } // 找到当前节点和右子节点中的最小值
        if (minidx == cur) break; // 如果当前节点是最小值，退出循环
        float tmp = arr[cur]; arr[cur] = arr[minidx]; arr[minidx] = tmp; cur = minidx;  // 交换当前节点和最小值节点, 更新 cur 为新的索引
    }
}
void pushHeap(float *arr, int *size, float x) {
    if ((*size) >= MAX_SIZE) return; // 如果堆已满，直接返回
    arr[*size] = x; (*size)++; // 将新元素放在堆的最后一个位置
    heaptifyUp(arr, (*size) - 1); // 重新调整堆
}
void popHeap(float *arr, int *size, float *val) {
    if ((*size) <= 0) return; // 如果堆为空，直接返回
    *val = arr[0]; arr[0] = arr[(*size) - 1]; // 将堆的最后一个元素放在堆顶
    (*size)--; heaptifyDown(arr, *size, 0); // 重新调整堆
}
void freeHeap(float **arr) { if (*arr) { free(*arr); *arr = NULL; } }

[akiradavidsong]

parent函数通常实现为(i - 1) // 2,因为在数组表示的堆中,节点i的父节点索引是(i - 1) // 2。这里我想了一会儿才想起来

[FrierenGreatDemonLord]

Python 小提示：

heapq, deque 的导包

from collections import deque
import heapq

[FrierenGreatDemonLord]

C swap() 不使用第三方变量的实现

void swap(int* a, int* b) {
	*a ^= *b;   // a ^ b
	*b ^= *a;  // a ^ b ^ b = a
	*a ^= *b; // a ^ b ^ a = b
}

[scrazyakai]

Queue maxHeap = new PriorityQueue<>((a, b) -> b - a);
这里的maxHeap是PriorityQueue，根据我查找的资料PriorityQueue不提供get,为什么siftUp/Down（）中的maxHeap能使用get()，是默认转换成ArrayList的了嘛？

[zhuiguang49]

请教一下大家元素入堆操作的C++代码部分：

/* 元素入堆 */
void push(int val) {
    // 添加节点
    maxHeap.push_back(val);
    // 从底至顶堆化
    siftUp(size() - 1);
}

/* 从节点 i 开始，从底至顶堆化 */
void siftUp(int i) {
    while (true) {
        // 获取节点 i 的父节点
        int p = parent(i);
        // 当“越过根节点”或“节点无须修复”时，结束堆化
        if (p < 0 || maxHeap[i] <= maxHeap[p])
            break;
        // 交换两节点
        swap(maxHeap[i], maxHeap[p]);
        // 循环向上堆化
        i = p;
    }
}

为什么可以直接使用size()，应当使用maxHeap.size()？编译器会自动将myHeap作为目标吗？

---

看了一下github仓库clone下来的代码，是定义了一个size函数return maxHeap.size()

/* 获取堆大小 */
    int size() {
        return maxHeap.size();
    }

感觉还是容易造成一点混淆的，因为有的读者可能会像我一样主要看网站和书，偶尔去看看完整的代码

[ChitandaEru520]

在8.1.1的代码里已经定义了int size = maxHeap.size()

[zhuiguang49]

应该并非如此，8.1.1的代码是用STL实现的，我指的代码是不借助STL自己实现的，我上面指出了这个问题，定义了一个size()函数

[ChitandaEru520]

你是对的，我的理解有误