The Order Property

Recall the order property: every node has priority at least as high as its children. When a smaller value means higher priority, that means no node holds a value larger than its children. Here is a tree that satisfies it:

               ╭───╮
               │ 2 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 5 │               │ 4 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 9 │     │ 7 │      │ 6 │
╰───╯     ╰───╯      ╰───╯

Check any node against its children: 2 is smaller than 5 and 4, 5 is smaller than 9 and 7, and 4 is smaller than 6. The smallest value, 2, sits at the root. No value can outrank the root, because every other node has a parent with priority at least as high, and following parents upward from any node always ends at the root.

Here is a tree that breaks the rule:

               ╭───╮
               │ 2 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │░5░│               │ 4 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 9 │     │░3░│      │ 6 │
╰───╯     ╰───╯      ╰───╯

The 3 sits below the 5, but 3 is smaller than 5, so the child outranks its parent. The order property is broken at that node, and this tree is not a heap.

Min-heaps and max-heaps

The first tree on this page is a min-heap: it keeps the smallest value at the root.

If a larger value means higher priority instead, then every node holds a value no smaller than its children, and the largest value sits at the root. That is a max-heap.

These are the heap forms of the min priority queue and the max priority queue from the specification, and the comparator decides which one we get.

A heap is not a binary search tree

Both a heap and a binary search tree are binary trees with an ordering rule. In a binary search tree, every node’s value is larger than every value in its left subtree and smaller than every value in its right subtree. That rule orders the whole tree from left to right. The order property is much weaker. It compares a node only against its own children and says nothing about how nodes on different branches compare.

Look again at the min-heap above. The root’s left child, 5, is larger than the root’s right child, 4, so the children are not in left-to-right order. And 9, on the left branch, is larger than 6 on the right branch. A binary search tree could never hold its values like this.

peek

Because of the order property, peek reads the root and returns its value. It does not search, and it does not change the tree. On the min-heap below, peek returns 1:

               ╭───╮
               │░1░│
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 3 │               │ 2 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 5 │     │ 4 │      │ 8 │
╰───╯     ╰───╯      ╰───╯

peek reads one node however many elements the heap holds, so it is $O(1)$. If the heap is empty there is no root, so peek throws a NoSuchElementException, as the specification requires.