父节点 r
左子节点2r+1
右子节点2r+2
叶节点数n/2
class Solution {
public:
/**
* @param A an integer array
* @return void
*/
void sortIntegers2(vector<int>& A) {
// Write your code here
/*
vector<int>temp(A.size(),0);
mergeSort(A,temp,0,A.size()-1);
*/
//quickSort(A,0,A.size()-1);
headSort(A);
}
void headSort(vector<int>& A){
int n = A.size();
//从最后一个不是叶节点的点开始调整
for(int i = n/2-1;i>=0;i--) {
headAdjust(A,i,n);
}
for(int i = n-1;i>0;i--){
A[0] = A[i]^A[0];
A[i] = A[i]^A[0];
A[0] = A[i]^A[0];
headAdjust(A,0,i);
}
}
//向下调整堆
void headAdjust(vector<int>& A,int index,int length) {
int i = index;
int j = 2*index+1;
while(j<length) {
if(j+1<length&&A[j+1]>A[j]) {
j++;
}
if(A[i]<A[j]) {
A[i] = A[i]^A[j];
A[j] = A[i]^A[j];
A[i] = A[i]^A[j];
} else {
break;
}
i = j;
j = 2*i+1;
}
}
}
