堆排序

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;

}