remove: Replace the Root and Sink Down

remove takes out the highest-priority element, which is the root. Removing the root leaves the top of the tree empty, and we have to fill it so that the result is still a valid heap.

Start with the structure property. A heap is a complete binary tree, so the only node we can drop without leaving a gap is the last one, at the right end of the bottom level. So we take the root’s value out, then move the last node’s value into the empty root and drop the last slot. The tree stays complete.

Consider this heap. remove will take out 1, the root:

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

Move the last node, 8, into the root and drop its old slot:

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

But the order property is now broken. We fix this by letting 8 sink down.

Compare the new root with its children, 3 and 2:

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

Swap the node with the smaller of its two children, the one with higher priority. Here the smaller child is 2, and 2 outranks 8, so they swap:

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

Now 8 has one child, 4. Compare them:

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

4 outranks 8, so they swap:

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

8 is now a leaf, so remove stops.

Why sink to the smaller child

The child that moves up becomes the parent of the other child. The smaller child has priority at least as high as the larger one, so moving it up keeps the order property between the two. If we moved the larger child up instead, it would sit above the smaller child and break the order property.

After each swap, the only place the order property can still fail is between the sinking value and its new children, so we keep sinking until no child outranks it or it reaches a leaf. Each swap moves the value down one level, so remove does at most one swap per level. The height of a heap is about $lo g n$ , as with add, so remove does $O (lo g n)$ swaps.

If the heap is empty there is no root to remove, so remove throws, as the specification requires.