heap
A heap is a binary tree tuned for one job: always knowing the smallest (or largest) item, instantly. It is not a search tree — it makes a much weaker promise, the heap property: every parent is less than or equal to its children (a min-heap) or greater than or equal to them (a max-heap). Nothing is said about left versus right siblings, so the heap is only partly sorted — just enough to keep the extreme element pinned at the root.
Two design choices make it fast. First, a heap is a complete binary tree: every level is full except possibly the last, which fills left to right. That perfect shape means the height is always about log n, with no risk of degenerating. Second, because the shape is so regular, you do not need pointers at all — you store the heap in a plain array, where the children of index i sit at 2i+1 and 2i+2 and the parent at (i-1)/2. The tree is implicit in the arithmetic.
Inserting adds the new item at the end and lets it bubble up past any parent it beats; removing the top swaps in the last item and lets it sift down to its proper level. Each fix walks one root-to-leaf path, so insert and extract-min/max both cost O(log n), while peeking at the top is O(1) since it is just the first array slot. That mix is exactly what a priority queue needs, and reading items out repeatedly is the heart of heapsort.
// min-heap stored in vector<int> h
void push(vector<int>& h, int x) {
h.push_back(x);
int i = h.size() - 1;
while (i > 0 && h[(i - 1) / 2] > h[i]) {
swap(h[i], h[(i - 1) / 2]); // sift up
i = (i - 1) / 2;
}
}Array-backed heap: insert appends then sifts up, an O(log n) operation.
A heap only finds the single min or max fast — it cannot search for an arbitrary key in O(log n); that is a binary-search-tree's job.