a binary tree inside an array, so it does not use parent/child pointers. - heap / std::make_heap

Key Properties

• find min in $O(1)$
• insert in $O(ln N)$
• delete min in $O(ln N)$
• But search is $O(N)$

Common uses for heap

• To build priority queues.
• To support heap sorts.
• To compute the nth minimum (or maximum) element(s) of a collection quickly.
• To impress your non-programmer friends.

There are two kinds of heaps: a max-heap and a min-heap which are different by the order in which they store the tree nodes.

In a max-heap, parent nodes have a greater value than each of their children. In a min-heap, every parent node has a smaller value than its child nodes. This is called the “heap property”, and it is true for every single node in the tree.

A sorted array from low-to-high is a valid min-heap.

see also

• Beating std::sort - Andrei
• Finding the first n largest elements in an array
• Fibonacci heap - has a better amortized running time than many other priority queue data structures.