3.11 Heap Sort

1. Heap Sort

heap.md Build heap + delete

2. Characteristics

• Stability: unstable
• Time: O(nlogn)
• Space: O(1)

3. Implementation

//O(NlogN)
func HeapSort(data []model.Comparable) {
	length := len(data)
	heapify(data, length)
	// A variant of extractMax
	// Put the largest value at the last position (i), then adjust the first i-1 positions
	// After processing, the array is in ascending order
	for i := length - 1; i > 0; i-- {
		util.Swap(data, 0, i)
		siftDown(data, 0, i)
	}
}

//O(logN)
func siftDown(data []model.Comparable, parentIndex int, length int) {
	// Stop at half because nodes from here have no children
	half := length / 2
	for parentIndex < half {
		leftChildIndex := leftChild(parentIndex)
		rightChildIndex := rightChild(parentIndex)

		// First assume the left child is larger
		maxIndex := leftChildIndex
		maxChild := data[maxIndex]
		// If the right child exists and is larger, update maxXXX
		if rightChildIndex < length {
			rightChild := data[rightChildIndex]
			if rightChild.CompareTo(maxChild) > 0 {
				maxChild = rightChild
				maxIndex = rightChildIndex
			}
		}

		parent := data[parentIndex]
		if maxChild.CompareTo(parent) <= 0 {
			break
		}

		// Swap the parent with the larger child
		util.Swap(data, parentIndex, maxIndex)
		parentIndex = maxIndex
	}

}

// O(N)
func heapify(data []model.Comparable, length int) {
	// Start from nodes with children and sift down to maintain the heap property
	for i := length>>1 - 1; i >= 0; i-- {
		siftDown(data, i, length)
	}
}

// Get the index of the left child
func leftChild(index int) int {
	return index*2 + 1
}

// Get the index of the right child
func rightChild(index int) int {
	return index*2 + 2
}

3.1. Test

func TestHeapSort(t *testing.T) {
	e0 := model.NewElement(0)
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)

	data := []model.Comparable{e3, e4, e0, e1, e2, e3, e3, e0, e1}
	fmt.Println(data)

	HeapSort(data)
	fmt.Println(data)
}

4. References

• Sorting Algorithm Stability - Baidu Baike
• Heap Sort - Wikipedia