Example 1: heap sort
function heapify(list, size, index) {
let largest = index;
let left = index * 2 + 1;
let right = left + 1;
if (left < size && list[left] > list[largest]) {
largest = left;
}
if (right < size && list[right] > list[largest]) {
largest = right;
}
if (largest !== index) {
[list[index], list[largest]] = [list[largest], list[index]];
heapify(list, size, largest);
}
return list;
}
function heapsort(list) {
const size = list.length;
let index = ~~(size / 2 - 1);
let last = size - 1;
while (index >= 0) {
heapify(list, size, --index);
}
while (last >= 0) {
[list[0], list[last]] = [list[last], list[0]];
heapify(list, --last, 0);
}
return list;
}
heapsort([4, 7, 2, 6, 4, 1, 8, 3]);
Example 2: heap sort
# Heap Sort in python
def heapify(arr, n, i):
# Find largest among root and children
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# If root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d " % arr[i], end='')