gistfile1.md

This is a heapsort I did from memory a few days ago. The main thing about it is that the array starts out with 0 items in the heap, where everything is in the array, unsorted. Then, using no extra space, move each item into the heap, and ensure that the parent is never less than any child. By the time we have put everything into the heap, it is "heapified". It is a priority queue, where the item at the top, at index 0 is the greatest element.

We then swap out the greatest item to the next item in the list, from the right. Every time we remove an element, we make sure that the top item bubbles down, until the heap property is restored. This allows us to continually swap out the highest item in the heap until the heap is gone, and the array is sorted as a side-effect.

• O(n lg(n)) is the worst and best case
• Note that QuickSort has low constants, but it's as bad as Bubblesort in the case where data is already sorted
• Therefore, when there are real-time safety concerns, you should not use QuickSort.
• This is a useful re-sorting algorithm, where you can continually push items into this and pull them out in the required order.
• For the sort, it is a greatest-item at the top of the heap due to our goal of using it to sort
• But we could require the heap to have the lowest item at the top, and have this be more like a queue, where lowest item comes out first until it is empty. This would be an excellent choice for clients writing values into a channel, and another process consumes the values out of a channel. In that case, all inserted items are pulled out in highest-known-value order.

package main

import "fmt"

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 |
		~float32 | ~float64 | ~string
}

func assertIsHeap[T Ordered](arr []T, sz int) {
	for at := 0; at <= sz; at++ {
		up := ((at + 1) >> 1) - 1
		if at > 0 {
			if arr[up] < arr[at] {
				panic(fmt.Sprintf("not a heap. %v above %v", arr[up], arr[at]))
			}
		}
	}
}

func HeapSort[T Ordered](arr []T) {

	// we split between in-heap and not in heap. in-heap is to the left of heapSize
	// walk O(n) items not in the heap
	for heapSize := 0; heapSize < len(arr); heapSize++ {
		// we think of array indices as starting from 1 in this algorithm
		// if they were 1 based:
		// here. up(here) = here/2. left(here) = here*2. right(here) = here*2+1
		// but because our arrays start at 0, we adjust
		here := heapSize
		for {
			// locate potential peers, bubble up O(lg n)
			up := ((here + 1) >> 1) - 1
			if up >= 0 {
				if arr[up] < arr[here] {
					arr[up], arr[here] = arr[here], arr[up]
					here = up
					continue
				}
			}
			break
		}
	}
	//assertIsHeap(arr, len(arr)-1)
	// Now the array is a priority heap with max at top, keep popping out
	// highest item to build the list of items in reverse until the heap is gone
	for heapLast := len(arr) - 1; heapLast >= 0; heapLast-- {
		arr[heapLast], arr[0] = arr[0], arr[heapLast]
		here := 0
		for {
			left := ((here + 1) << 1) - 1
			right := left + 1
			if right < heapLast && arr[right] >= arr[left] && arr[here] < arr[right] {
				arr[right], arr[here] = arr[here], arr[right]
				here = right
				continue
			} else if left < heapLast && arr[here] < arr[left] {
				arr[left], arr[here] = arr[here], arr[left]
				here = left
				continue
			}
			break
		}
	}
}

func main() {
	arr := []int{3, 5, 20, 20, 99, 50, 22, 19, 18, 17, 16, 15, 14, 1, 2, 3, 44, 15, 33, 44, 33, 9, 20, 20, 22, 19, 7, 1, 6}
	fmt.Printf("unsorted: %v\n", arr)
	HeapSort(arr)
	fmt.Printf("sorted:   %v\n", arr)
}