https://tool.lu/coderunner/
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
void shiftDown(vector<int> &nums, int index) {? // 建堆的過程中下沉
int left = index*2+1;
int right = index*2+2;
while(index < nums.size()) {
if(nums[index] >= max(nums[left], nums[right])) return;
if(nums[left] > nums[right]) {
swap(nums[index], nums[left]);
index = left;
}
else {
swap(nums[index], nums[right]);
index = right;
}
left = index*2+1;
right = index*2+2;
}
}
void shiftUp(vector<int> &nums) { // 在末尾插入一個元素后伪窖， 進行上浮操作
if(nums.size() == 0) return;
int index = nums.size()-1;
while(index >= 0) {
int parent = (index - 1)/2;
if(nums[parent] >= nums[index]) return;
swap(nums[parent], nums[index]);
index = parent;
}
}
void buildHeap(vector<int> &nums) {? // 建堆
for(int i = nums.size()/2; i>=0; i--) {
shiftDown(nums, i);
}
}
void fakeData(vector<int> &nums, int n) {
for(int i =0; i<n; i++) {
nums.push_back(rand()%1000);
}
}
void printVec(const vector<int> &nums) {
for(int i=0;i<nums.size(); i++) {
cout<<nums[i]<<" ";
}
cout<<endl;
}
int main() {
vector<int> nums;
fakeData(nums, 3);
printVec(nums);
buildHeap(nums);
printVec(nums);
nums.push_back(rand()%1000);
shiftUp(nums);
printVec(nums);
return 0;
}
