Regarding quicksort 3-way #

Used for when there is a lot of duplicate keys, for example sorting by US state.

Heap and priority queues #

Index starts at 1 so the math to find the child or parent works.

Size starts at 0, but is incremented BEFORE it is used for the pq position.

Space complexity of swim method is O(1).

Swap root and highest index and decrement index to break it off

Choose the bigger child when sink starts

Swap item if bigger, choosing bigger child to compare to

Sink space complexity is O(1).

Best case running time is O(1) (if there are only 2 children). Worst case is O(lg(n)).

It sinks tree by tree