Heap

A binary heap is a complete binary tree stored in a plain array: the children of index i sit at 2i + 1 and 2i + 2, and its parent at ⌊(i − 1) / 2⌋. Every parent beats its children (smaller in a min-heap, larger in a max-heap), so the best value is always at the root. Insert sifts a new value up; extracting the root moves the last value to the top and sifts it down.