7. Sorting

Heap sort

0 of 5 activities0%

Reading 1

Heapify then extract

Open

Heap sort builds a max-heap in O(n), then swaps the root with the end and heapifies down, shrinking the heap.

Time O(n log n), in-place (aside from recursion/stack), not stable.

Connects heaps to sorting.

// after build-heap:
// for i=n-1..1: swap(a[0],a[i]); siftDown(0,i)

Check 2

Open

Heap sort time is

Fill in 3

Open

Try it 4

Open

For heap index i, parent is (i-1)/2.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read i (i>=1). Print parent index (i-1)/2 in a 0-based heap array.

main.cpp

Loading editor…