- 大堆根基本概念
- 建立大堆根的重要函数
- 全部代码
- C++中priority_queue的关键代码
- 参考&感谢
- 堆顶的元素是最大的
- 根节点比左右子节点的数大
- 大堆根原本是一棵完全二叉树，二叉树中没有空缺。
- 可以使用数组来存储这棵完全二叉树
- 树和数组下标的关系（从下标0开始）：第i位置的左节点为2i+1,右节点为2i+2,父节点为(i-1)/2
- 堆和数组的关系
- 大堆根插入函数（从后调整）：
目的：
1.在[0,index-1]段满足大堆根的规则，再加入一个元素，则需要调整；
2.调整原则：将index元素与其父节点比较，index元素大，则需要交换；并循环与向上的父节点比较；
//在大堆根后面index位置的元素进行调整
void heapInsert(vector& arr, int index)
{//将index和他的根节点比较，大于的话就交换
while(arr[index] > arr[(index-1)/2])
{//index=0时会终止循环
swap(arr[index], arr[(index-1)/2]);
index = (index - 1) / 2;
}
}
- 大堆根调整函数（从前调整）：
目的：
1.在删除元素（堆顶）时，需要将堆顶元素（下标为0的元素）与数组尾元素交换，然后再删除数组尾的元素
2.调整原则：将index与他左/右节点最大的元素交换，并循环向下做同样的操作
//调整index位置的元素，一般是第一个index=0
//[0,heapSize)为大堆根段，具体理解可以结合全部代码中的堆排序函数heapSort()
void heapAdj(vector& arr, int index, int heapSize)
{//将index与他左/右节点最大的交换
int left = 2 * index + 1; // index的左节点
while(left < heapSize)
{
//寻找左右节点的最大值下标
int large = left + 1 < heapSize && arr[left+1] > arr[left] ? left + 1 : left;
//左右最大值和index比较
large = arr[large] > arr[index] ? large : index;
if (large == index)
{
break;
}
swap(arr[large], arr[index]);
index = large;
left = 2 * index + 1;
}
}
全部代码
- main.cpp:
#include#include "bigheap.h" using namespace std; int main() { vector v{1, 2, 5, 6}; BigHeap bh(v); bh.push(10); bh.push(4); bh.push(3); cout << "大堆根："; for (auto a : bh.get()) { cout << a << " "; } cout << endl; cout << "大堆根弹出的顺序：" << endl; int n = bh.size(); for (int i = 0; i < n; i++) { cout << "top: " << bh.top() << endl; bh.pop(); } vector v1{1, 2, 45, 20, 5, 6}; cout << "堆排序："; bh.heapSort(v1); for (auto a : v1) { cout << a << " "; } cout << "你好" << endl; return 0; }
- 运行结果
大堆根：10 6 4 1 5 2 3 大堆根弹出的顺序： top: 10 top: 6 top: 5 top: 4 top: 3 top: 2 top: 1 堆排序：1 2 5 6 20 45 你好
- bigheap.h:
// 大堆根 // Created by Ycq on 2022/6/8. // #ifndef CLIONTEST_BIGHEAP_H #define CLIONTEST_BIGHEAP_H #includeC++中priority_queue的关键代码using namespace std; // 建立大堆根 // 参考：https://blog.csdn.net/dream_follower/article/details/105202811 // 数组以下标0开始，第i位置的左节点为2i+1,右节点为2i+2,父节点为(i-1)/2 class BigHeap { private: vector vec; public: BigHeap(){} BigHeap(vector &v) : vec(v) { heapBuild(vec); } //返回大堆数组 vector get() { return vec; } //返回大堆顶 int top() { return vec[0]; } //删除堆顶 void pop() { swap(vec[0], vec[vec.size() - 1]); //将堆顶元素交换到数组尾部 vec.pop_back(); //删除尾部元素 heapAdj(vec, 0, vec.size()); //调整大堆 } //添加元素 void push(int x) { vec.push_back(x); heapInsert(vec, vec.size() - 1); } //vec的大小 int size() { return vec.size(); } //判空 bool empty() { return vec.empty(); } //在大堆根后面index位置的元素进行调整 void heapInsert(vector & arr, int index) {//将index和他的根节点比较，大于的话就交换 while(arr[index] > arr[(index-1)/2]) {//index=0时会终止循环 swap(arr[index], arr[(index-1)/2]); index = (index - 1) / 2; } } //调整index位置的元素，一般是第一个index=0 void heapAdj(vector & arr, int index, int heapSize) {//将index与他左/右节点最大的交换 int left = 2 * index + 1; // index的左节点 while(left < heapSize) { //寻找左右节点的最大值下标 int large = left + 1 < heapSize && arr[left+1] > arr[left] ? left + 1 : left; //左右最大值和index比较 large = arr[large] > arr[index] ? large : index; if (large == index) { break; } swap(arr[large], arr[index]); index = large; left = 2 * index + 1; } } //建大堆根 void heapBuild(vector & arr) { int n = arr.size(); if (n < 2) return; for (int i = 0; i < n; i++) {//建大堆根 heapInsert(arr, i); } } //堆排序, 不要给本对象的vec排序，由于使用的是引用传参，会改变vec，而使vec不满足大堆根的规则 void heapSort(vector & arr) {//其实就是依次把堆顶的元素放入数组尾部，每次heapSize减1（>0）,最后arr是升序 int n = arr.size(); heapBuild(arr); //将第一个（堆顶）元素和最后一个元素交换 swap(arr[0], arr[--n]); while(n > 0) { heapAdj(arr, 0, n); swap(arr[0], arr[--n]); } } }; #endif //CLIONTEST_BIGHEAP_H
make_heap(c.begin(),c.end(),comp); //是在构造函数中，使容器c中的元素生成大堆根（默认） template参考&感谢, class Compare = less > class priority_queue{ ... protected: Sequence c; // 底层容器 Compare comp; // 元素大小比较标准 public: bool empty() const {return c.empty();} size_type size() const {return c.size();} const_reference top() const {return c.front()} void push(const value_type& x) { c.push_back(x); push_heap(c.begin(), c.end(),comp); //在插入一个元素后，调整元素，使满足堆的规则 } void pop() { pop_heap(c.begin(), c.end(),comp); //将堆顶元素调整到c的末尾，并使其使满足堆的规则，然后删除最后一个元素 c.pop_back(); } };
主要参考这里写的
