第二步下沉和弹出

加上 sift_down 和 pop_top。把两次弹出的结果拼起来输出(用 / 隔开)。 (本题用 g++ -std=c++17 -O0 编译。)

开始练习 →

第三步从乱序数组直接建堆

加上 build_heap:不用一个个 push,从最后一个有孩子的节点倒着下沉。建好之后把整个数组拼起来输出。 (本题用 g++ -std=c++17 -O0 编译。)

开始练习 →

第四步拿它去求 Top-K

用前面写好的堆求前 3 大,把结果拼起来输出(用 / 隔开)。 (本题用 g++ -std=c++17 -O0 编译。)

开始练习 →

交付堆加 Top-K 加调度

这是这条路线的最终作品。把 push_up / sift_down / pop_top / build_heap / check_heap 和按优先级出队的 pop_max 全写出来,然后一次验完五条:五个数插完,堆顶是 24、一共 5 个

开始练习 →

check 说超时了先想什么

~/check 提示「结果对,但超时了」,最该先想的是【0】。

开始练习 →

补写堆的下沉

场景:实验机上 ~/work/heap/sift.cpp 读入一串整数,就地建成大顶堆后输出整个数组。建堆要用的 sift_down 还没写。 任务:补全 sift_down(和较大的孩子换、一路下沉),让建堆结果正确。make 编译,./

开始练习 →

三十万个数取前 K 大

场景:~/work/heap/topk.cpp 读入 n、k 和 n 个整数,从大到小输出最大的 k 个。结果对,可它用插入排序把所有数全排了一遍,n 一大就超时。 任务:改写 topk.cpp,让 n = 300000 时也能在 1 秒内

开始练习 →

写一个大根堆类

场景:~/work/heap/ops.cpp 按指令操作一个大根堆:push x、pop(输出弹出的值)、top(输出堆顶)。MaxHeap 的 push / pop / top 还没写。 任务:补全 MaxHeap。程序最后会自己检查一次

开始练习 →

修好写反的比较器

场景:~/work/heap/sched.cpp 按优先级调度任务:每行「优先级 任务名」,优先级大的先处理,同级先进来的先处理。可它现在总是先处理最不急的。 任务:修好比较器 ByPrio,让调度顺序正确。make 编译后用 sample

开始练习 →

修好错位的下标公式

场景:~/work/heap/sort.cpp 把一串整数逐个放进手写的大根堆,再逐个弹出,应该得到从大到小的序列。可结果总是乱的。 任务:找出并修好堆里写错的下标公式(不止一处)。make 编译后用 sample.txt 自测。 可操作范

开始练习 →