Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Heap Sort
Explanation
Heap sort is a sorting algorithm that works by first building a heap from the input array
...
The root node of the heap is the largest (max-heap) or smallest (min-heap)
element in the heap
...
The heap is then rebuilt without the
extracted element
...


Algorithm

def heap_sort(array):
build_heap(array)
for i in range(len(array) - 1, 0, -1):
swap(array[0], array[i])
heapify(array, 0, i - 1)

def build_heap(array):
for i in range(len(array) // 2, -1, -1):
heapify(array, i, len(array) - 1)

def heapify(array, index, end):
largest = index
left = 2 * index + 1

right = 2 * index + 2

if left <= end and array[left] > array[largest]:
largest = left

if right <= end and array[right] > array[largest]:
largest = right

if largest != index:
swap(array[index], array[largest])
heapify(array, largest, end)

Time complexity
The time complexity of heap sort is O(n log n), where n is thesize of the array
...


Advantages:
 Faster than other sorting algorithms such as bubble sort, selection sort, and insertion sort
...


Disadvantages
 Heap sort is not an in-place sorting algorithm
...

 Heap sort can be less efficient for small arrays
...




---