#include <iostream> #include <vector> using namespace std; template<typename P> class Heap { private: vector<P> heap_elem{-1};//堆容器, 使得堆的编号从1开始 int maxmin_heap;//选择大\小根堆 void up_adjust(int now) {//上浮调整(默认大根堆) while (now > 1 && heap_elem[now] > heap_elem[now / 2]) { swap(heap_elem[now], heap_elem[now / 2]); now = now / 2; } }; void down_adjust(P &top, int now) {//下沉调整 heap_elem[now] = top; int next; while (now * 2 <= heap_elem.size() - 1) { if (now * 2 + 1 > heap_elem.size() - 1) { next = now * 2; } else { next = heap_elem[now * 2] > heap_elem[now * 2 + 1] ? now * 2 : now * 2 + 1; } if (heap_elem[next] > heap_elem[now]) { swap(heap_elem[next], heap_elem[now]); now = next; } else { break; } } }; public: Heap(int m) {//构造堆 maxmin_heap = m;//default max_heap }; P getTop() {//弹获取堆顶元素 if (heap_elem.size() > 1) return heap_elem[1] * maxmin_heap; return heap_elem[0];//堆为空 } bool empty() {//判断堆空 return heap_elem.size() == 1; } void push(P x) {//送元素入堆 heap_elem.push_back(x * maxmin_heap); int now = heap_elem.size() - 1; up_adjust(now); }; P pop() {//堆顶元素弹出 P res = getTop(); P top = heap_elem.back(); heap_elem.pop_back(); int now = 1; down_adjust(top, now); cout << "pop " << res << " successfully." << endl; return res; }; int size() { return heap_elem.size() - 1; } void print() { for (int i = 1; i < heap_elem.size(); i++) { cout << heap_elem[i] * maxmin_heap << ' '; } cout << endl; } }; int main() { //Topk测试没问题 int max_heap = 1, min_heap = -1; Heap<int> h(min_heap);//可更改为min_heap,来构建小根堆 int x; for (int i = 0; i < 10; ++i) { x = rand() % 100; h.push(x); cout << "x: " << x << endl; h.print(); } h.pop(); h.print(); return 0; }
0