Heap Sort

Heap sort is a comparison based sorting algorithm. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

									Public Shared Sub HeapSort(ByRef data As Integer())
	Dim heapSize As Integer = data.Length

	For p As Integer = (heapSize - 1) \ 2 To 0 Step -1
		MaxHeapify(data, heapSize, p)
	Next

	For i As Integer = data.Length - 1 To 1 Step -1
		Dim temp As Integer = data(i)
		data(i) = data(0)
		data(0) = temp

		heapSize -= 1
		MaxHeapify(data, heapSize, 0)
	Next
End Sub

Private Shared Sub MaxHeapify(ByRef data As Integer(), heapSize As Integer, index As Integer)
	Dim left As Integer = (index + 1) * 2 - 1
	Dim right As Integer = (index + 1) * 2
	Dim largest As Integer = 0

	If left < heapSize AndAlso data(left) > data(index) Then
		largest = left
	Else
		largest = index
	End If

	If right < heapSize AndAlso data(right) > data(largest) Then
		largest = right
	End If

	If largest <> index Then
		Dim temp As Integer = data(index)
		data(index) = data(largest)
		data(largest) = temp

		MaxHeapify(data, heapSize, largest)
	End If
End Sub

Example

									Dim data() As Integer = { -1, 25, -58964, 8547, -119, 0, 78596 }
HeapSort(data)

Output