// Java
static void heapify(int[] array, int length, int i) {
int left = 2 * i + 1, right = 2 * i + 2；
int largest = i;
if (left < length && array[left] > array[largest]) {
largest = left;
}
if (right < length && array[right] > array[largest]) {
largest = right;
}
if (largest != i) {
int temp = array[i]; array[i] = array[largest]; array[largest] = temp;
heapify(array, length, largest);
}
}
public static void heapSort(int[] array) {
if (array.length == 0) return;
int length = array.length;
for (int i = length / 2-1; i >= 0; i-)
heapify(array, length, i);
for (int i = length - 1; i >= 0; i--) {
int temp = array[0]; array[0] = array[i]; array[i] = temp;
heapify(array, i, 0);
}
}
#Python
def heapify(parent_index, length, nums):
temp = nums[parent_index]
child_index = 2*parent_index+1
while child_index < length:
if child_index+1 < length and nums[child_index+1] > nums[child_index]:
child_index = child_index+1
if temp > nums[child_index]:
break
nums[parent_index] = nums[child_index]
parent_index = child_index
child_index = 2*parent_index + 1
nums[parent_index] = temp
def heapsort(nums):
for i in range((len(nums)-2)//2, -1, -1):
heapify(i, len(nums), nums)
for j in range(len(nums)-1, 0, -1):
nums[j], nums[0] = nums[0], nums[j]
heapify(0, j, nums)
C/C++
void heapify(vector<int> &array, int length, int i) {
int left = 2 * i + 1, right = 2 * i + 2;
int largest = i;
if (left < length && array[left] > array[largest]) {
largest = left;
}
if (right < length && array[right] > array[largest]) {
largest = right;
}
if (largest != i) {
int temp = array[i]; array[i] = array[largest]; array[largest] = temp;
heapify(array, length, largest);
}
return ;
}
void heapSort(vector<int> &array) {
if (array.size() == 0) return ;
int length = array.size();
for (int i = length / 2 - 1; i >= 0; i--)
heapify(array, length, i);
for (int i = length - 1; i >= 0; i--) {
int temp = array[0]; array[0] = array[i]; array[i] = temp;
heapify(array, i, 0);
}
return ;
}
// Javascript
function heapSort(arr) {
if (arr.length === 0) return;
let len = arr.length;
// 建堆
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(arr, len, i);
}
// 排序
for (let i = len - 1; i >= 0; i--) {
// 堆顶元素与最后一个互换
[arr[0], arr[i]] = [arr[i], arr[0]];
// 对 0 ～ i 的数组建堆
heapify(arr, i, 0);
}
}
function heapify(arr, len, i) {
let left = i * 2 + 1;
let right = i * 2 + 2;
let largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, len, largest);
}
}