int parent(const int &root) {
return root / 2;
}
int left(const int &root) {
return root * 2;
}
int right(const int &root) {
return root * 2 + 1;
}
void max_heapify(vector<int> &nums, int i, const int &heap_size) {
int largest;
while (i <= heap_size) {
largest = i;
if (left(i) <= heap_size && nums[left(i)] > nums[i])
largest = left(i);
if (right(i) <= heap_size && nums[right(i)] > nums[largest])
largest = right(i);
if (largest == i)
break;
int temp = nums[largest];
nums[largest] = nums[i];
nums[i] = temp;
i = largest;
}
}
void build_max_heap(vector<int> &nums) {
for (int i((nums.size() - 1) / 2); i >= 1; --i)
max_heapify(nums, i, nums.size() - 1);
}
void heap_sort(vector<int> &nums) {
nums.insert(nums.begin(), 0);//这里为了下标运算与书上一致，在数列头插了一个零，真正的待排序数列下标从1开始
build_max_heap(nums);
for (int i(nums.size() - 1); i > 1; --i) {
int temp = nums[i];
nums[i] = nums[1];
nums[1] = temp;
max_heapify(nums, 1, i - 1);
}
nums.erase(nums.begin());
}
