-
Notifications
You must be signed in to change notification settings - Fork 0
/
堆排序.cpp
61 lines (60 loc) · 1.61 KB
/
堆排序.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
// 设node的index = i
// 那么node的parent = (i-1)/2
// child1=i*2+1
// child2=i*2+1
// https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=7050648321157556627
void printArr(vector<int> & nums){
for(auto e:nums){
cout<<e<<' ';
}
cout<<endl;
}
void heapify(vector<int>& arr,int boundary,int index){
if(index>=boundary)return ;
int childL = index*2 +1;
int childR = index*2 +2;
int indexMax = index;
if(childL<=boundary && arr[childL]>arr[indexMax])indexMax=childL;
if(childR<=boundary && arr[childR]>arr[indexMax])indexMax=childR;
if(indexMax!=index){
swap(arr[index],arr[indexMax]);
// 递归向下调整Heap
// cout<<"index: "<<index<<endl;
// printArr(arr);
heapify(arr,boundary,indexMax);
}
}
void buildHeap(vector<int> & arr){
int n = arr.size()-1;
// 从最后的节点的parent往回build,确保从底下就是堆
for(int i=(n-1)/2 ; i>=0 ; i--){
heapify(arr,n,i);
}
}
void heapSort(vector<int> & arr){
buildHeap(arr);
printArr(arr);
int n=arr.size()-1;
for(int i=0;i<n;i++){
// 交换堆顶和堆尾,堆顶放置到最后(最大的往后放)
cout<<"swaping: "<<arr[0]<<' '<<arr[n-i]<<endl;
swap(arr[0],arr[n-i]);
cout<<"boundary: "<<n-i-1<<endl;
heapify(arr,n-i-1,0);
printArr(arr);
}
}
int main(){
vector<int> nums1 = {1,4,3,5,7};
heapify(nums1,nums1.size()-1,0);
printArr(nums1);
cout<<"--------------"<<endl;
heapSort(nums1);
printArr(nums1);
return 0;
}