堆,顾名思义,是长得像个草堆一样的数据结构。但在计算机存储里面,堆一般使用数组来表示。
按照堆的性质区分,可分为大顶堆,小顶堆。
大顶堆:所有的parent节点值都要大于
其child节点。
小顶堆:所有的parent节点值都要小于
其child节点。
堆有三个主要的操作:
堆引申出来的堆排序
如果要对数组进行升序排序,需要使用大顶堆。建立大顶堆后,将大顶堆的堆顶元素与堆末尾元素进行交换,然后再调整交换后的堆顶,不过此时堆的大小减一,最后位置元素不可参与堆调整范围里。如此反复。
HeapSort(A):
BUild_Max_Heap(A)
for i = A.lenght to 2: # 当堆只剩一个元素,不用调整了,所以到2
swap(A[1],A[i])# 交换堆顶元素与堆末尾元素
A.heap_size = A.heap_size-1
Max_Heaplify(A,1)
#include<bits/stdc++.h>
using namespace std;
void printVec(vector<int> nums)
{
for (int i = 0; i < nums.size(); ++i)
cout << nums[i] << " ";
cout << endl;
}
int main()
{
locale::global(std::locale(""));
vector<int> v1 = { 20, 30, 40, 25, 15 };
cout << "原始数组v1:";
printVec(v1);
make_heap(v1.begin(), v1.end());//将vector v1弄成了大顶堆,v1还是vector,不过具有heap性质
cout << "make_heap以后:";
printVec(v1);
//make_heap(v1.begin(), v1.end(),greater<int>());//将vector v1弄成了大顶堆
//cout << "堆顶元素" << v1.front() << endl;
v1.push_back(50);
push_heap(v1.begin(), v1.end());
cout << "push 一个元素以后:";
printVec(v1);
//push_heap之前还是push_back了一下,这么看来和make_heap好像没啥区别
pop_heap(v1.begin(), v1.end());//将堆顶元素与最后一个元素交换,并未真正删除
v1.pop_back();
cout << "pop_heap以后:";
printVec(v1);
//判定vector v1是否为堆
is_heap(v1.begin(), v1.end()) ?cout << "The container is heap " :cout << "The container is not heap";
cout << endl;
//堆排序。仅对已经是堆的v1进行堆排序,不然出错,结果不对
sort_heap(v1.begin(), v1.end());
cout << "堆排序之后: ";
for (int &x : v1)
cout << x << " ";
cout << endl;
vector<int> v2 = {80,30, 45,1, 55, 15 };
cout << "原始数组v2:";
printVec(v2);
auto it = is_heap_until(v2.begin(), v2.end());
// Displaying heap range elements
cout << "从v2开始到第一个不满足堆性质的元素: ";
for (auto it1 = v2.begin(); it1 != it; it1++)
cout << *it1 << " ";
return 0;
}
//升序队列
priority_queue <int,vector<int>,greater<int>> q;
for (int n : {1, 8, 5, 6, 3, 4, 0, 9, 7, 2})
q.push(n);
print_queue(q);
描述:给定一个数组,和一个K值,将数组中的一些元素拿出后再相加后再加入到数组中,一直到数组中所有元素都大于等于K。求这最小相加次数。
input:arr = {1 10 12 9 2 3} K = 6
输出:2
解释:首先将拿出数组中的1和2相加,得到3,再将3加入到数组中,数组变成了[3,10,12,9,3],然后再拿出3 和3,并相加,得到6,再将6加入到数组中,数组变成了[6,10,12,9],现在数组中的所有元素都大于等于6。因此,需要相加两次。
其实就是霍夫曼编码。用原数组建成一个小顶堆,之后取堆顶最小的两个元素,相加后再加入到堆中,一直到这个小顶堆的堆顶大于给定的K。
int countMinOps(vector<int>&nums, int k)
{
int ret = 0;
priority_queue<int, vector<int>, greater<int>>q;
for (auto i : nums)q.push(i);//建小顶堆
while (q.top() < k&&q.size()) {
int a = q.top();
q.pop();
int b= q.top();
q.pop();
q.push(a + b);
ret++;
}
return ret;
}