# 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//2, -1, -1):
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='')
function heap_root(input, i) {
/* to create MAX array */
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
// if left child is larger than root
if (left < array_length && input[left] > input[max]) {
max = left;
}
// if right child is larger than max
if (right < array_length && input[right] > input[max]) {
max = right;
}
// if max is not root
if (max != i) {
swap(input, i, max);
heap_root(input, max);
}
}
function swap(input, index_A, index_B) {
var temp = input[index_A];
input[index_A] = input[index_B];
input[index_B] = temp;
}
function heapSort(input) {
array_length = input.length;
// Building the heap
for (var i = Math.floor(array_length / 2); i >= 0; i -= 1) {
heap_root(input, i);
}
// One by one extract and put in place
for (i = input.length - 1; i > 0; i--) {
swap(input, 0, i);
array_length--;
heap_root(input, 0);
}
}