堆不要求整个数组有序,只需要关注堆顶,和堆排序不一样
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class MYHEAP {
public:
void push(int val) { //插入到末尾,往前调整
nums.push_back(val);
heapUp();
}
void pop() { //删除堆顶,往后调整
nums[0] = nums.back();
nums.pop_back();
heapDown();
}
void heapUp() //插入元素,从后往前调整
{
int index = nums.size() - 1;
int father = (index - 1) / 2;
while (index > 0) {
if (nums[index] < nums[father]) {
swap(nums[index], nums[father]);
index = father;
father = (father - 1) / 2;
}
else {
break;
}
}
}
void heapDown() //删除堆顶,从0往后调整
{
int index = 0;
int max_index = nums.size() - 1;
int lchild=0;
int rchild;
while (index < max_index) {
lchild = 2 * index + 1;
rchild = 2 * index + 2;
if (lchild > max_index) break; //不存在左孩子
else if (rchild > max_index) { //存在左孩子,不存在右孩子
if (nums[index] > nums[lchild]) {
swap(nums[index], nums[lchild]);
index = lchild;
}
else {
break;
}
}
else { //左右孩子都存在
int smaller = nums[lchild] <= nums[rchild] ? lchild : rchild;
if (nums[index] > nums[smaller]) {
swap(nums[index], nums[smaller]);
index = smaller;
}
else {
break;
}
}
}
}
void getTop() {
cout << nums[0]<<endl;
}
private:
vector<int> nums;
};
int main() {
vector<int> nums = { 2,1,6,4,3,7,0,11 };
MYHEAP heap;
for (int i = 0; i < 6; i++) {
heap.push(nums[i]);
heap.getTop();
}
heap.pop();
heap.getTop();
}
关于堆排序的文章在这里