Heaps

A heap is a complete binary tree that keeps the smallest value, a min-heap, or the largest, a max-heap, at the root. Complete means every level is full except possibly the last, which is filled from the left. That shape lets you store the tree in an array with no pointers.

For a node at index i, the parent sits at floor((i - 1) / 2), the left child at 2i + 1, and the right child at 2i + 2. Insert writes the new value at the end, then swaps it upward while it belongs above its parent. Removing the root moves the last value into that hole and swaps it downward until the order holds. Both are O(log n).

You reach for a heap when you repeatedly need the current extreme, not a fully sorted list. The kth largest value is the textbook case: keep a min-heap of size k, throw away anything smaller, and the root is the answer. Sorting the whole array also works. It orders more than you asked for.