PYTHON

heap sort

package sort

type MaxHeap struct {
	slice    []Comparable
	heapSize int
	indices  map[int]int
}

func buildMaxHeap(slice0 []int) MaxHeap {
	var slice []Comparable
	for _, i := range slice0 {
		slice = append(slice, Int(i))
	}
	h := MaxHeap{}
	h.Init(slice)
	return h
}

func (h *MaxHeap) Init(slice []Comparable) {
	if slice == nil {
		slice = make([]Comparable, 0)
	}

	h.slice = slice
	h.heapSize = len(slice)
	h.indices = make(map[int]int)
	h.Heapify()
}

func (h MaxHeap) Heapify() {
	for i, v := range h.slice {
		h.indices[v.Idx()] = i
	}
	for i := h.heapSize / 2; i >= 0; i-- {
		h.heapifyDown(i)
	}
}

func (h *MaxHeap) Pop() Comparable {
	if h.heapSize == 0 {
		return nil
	}

	i := h.slice[0]
	h.heapSize--

	h.slice[0] = h.slice[h.heapSize]
	h.updateidx(0)
	h.heapifyDown(0)

	h.slice = h.slice[0:h.heapSize]
	return i
}

func (h *MaxHeap) Push(i Comparable) {
	h.slice = append(h.slice, i)
	h.updateidx(h.heapSize)
	h.heapifyUp(h.heapSize)
	h.heapSize++
}

func (h MaxHeap) Size() int {
	return h.heapSize
}

func (h MaxHeap) Update(i Comparable) {
	h.slice[h.indices[i.Idx()]] = i
	h.heapifyUp(h.indices[i.Idx()])
	h.heapifyDown(h.indices[i.Idx()])
}

func (h MaxHeap) updateidx(i int) {
	h.indices[h.slice[i].Idx()] = i
}

func (h MaxHeap) heapifyUp(i int) {
	if i == 0 {
		return
	}
	p := i / 2

	if h.slice[i].More(h.slice[p]) {
		h.slice[i], h.slice[p] = h.slice[p], h.slice[i]
		h.updateidx(i)
		h.updateidx(p)
		h.heapifyUp(p)
	}
}

func (h MaxHeap) heapifyDown(i int) {
	l, r := 2*i+1, 2*i+2
	max := i

	if l < h.heapSize && h.slice[l].More(h.slice[max]) {
		max = l
	}
	if r < h.heapSize && h.slice[r].More(h.slice[max]) {
		max = r
	}
	if max != i {
		h.slice[i], h.slice[max] = h.slice[max], h.slice[i]
		h.updateidx(i)
		h.updateidx(max)
		h.heapifyDown(max)
	}
}

type Comparable interface {
	Idx() int
	More(interface{}) bool
}
type Int int

func (a Int) More(b interface{}) bool {
	return a > b.(Int)
}
func (a Int) Idx() int {
	return int(a)
}

func HeapSort(slice []int) []int {
	h := buildMaxHeap(slice)
	for i := len(h.slice) - 1; i >= 1; i-- {
		h.slice[0], h.slice[i] = h.slice[i], h.slice[0]
		h.heapSize--
		h.heapifyDown(0)
	}

	res := []int{}
	for _, i := range h.slice {
		res = append(res, int(i.(Int)))
	}
	return res
}

heap sort

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);
    }
}

How to perform heap sort?

"""
The below code provides an implementation 
for the heap sort algorithm 
(https://en.wikipedia.org/wiki/Heapsort). 
Sorting a list via heap sort is a two-step 
process:
1. In first step, transform the original list
into a heap. 
2. In second step, sort the list by placing
the values in order at end of list. 

Let n be the number of elements in list to sort.

Time complexity: O(nlog2(n))
Space complexity: O(1), sorting is done in place.
"""
from heapq import heapify


def heap_sort(list):
    n = len(list)
    # First step: turn list into a heap
    heapify(list)
    print(list)
    # Second step: repeatedly place next
    # smallest value at end of the list
    for idx in range(n-1, 0, -1):
        swap(0, idx, list)
        bubble_down(0, idx-1, list)


def swap(idx1, idx2, list):
    list[idx1], list[idx2] = list[idx2], list[idx1]


def bubble_down(current_idx, last_idx, heap):
    # Method used to restore heap order property when violated
    child_one_idx = current_idx * 2 + 1
    while child_one_idx <= last_idx:
        child_two_idx = current_idx * 2 + 2 if current_idx*2 + 2 <= last_idx else -1

        if child_two_idx > -1 and heap[child_two_idx] < heap[child_one_idx]:
            idx_to_swap = child_two_idx
        else:
            idx_to_swap = child_one_idx

        if heap[idx_to_swap] < heap[current_idx]:
            swap(current_idx, idx_to_swap, heap)
            current_idx = idx_to_swap
            child_one_idx = current_idx * 2 + 1
        else:
            return


list = [1, 10, 4, 3, 2]
heap_sort(list)
# Descending order
print(list)  # [10, 4, 3, 2, 1]
# Ascending order
list.reverse()
print(list)  # [1, 2, 3, 4, 10]