The `FindMin` member function locates the item with the smallest key
in a given priority queue
and the `DequeueMin` member function removes it from the queue.
Since the smallest item in a heap is found at the root,
the `FindMin` operation is easy to implement.
Program shows how it can be done.
Clearly, the running time of the `FindMin` operation is *O*(1).

**Program:** `LeftistHeap` Class `FindMin` Member Function Definitions

Since the smallest item in a heap is at the root,
the `DequeueMin` operation must delete the root node.
Since a leftist heap is a binary heap,
the root has at most two children.
In general when the root is deleted,
we are left with two non-empty leftist heaps.
Since we already have an efficient way to merge leftist heaps,
the solution is to simply merge the two children of the root
to obtain a single heap again!
Program shows how the `DequeueMin` operation
of the `LeftistHeap` class can be implemented.

**Program:** `LeftistHeap` Class `DequeueMin` Member Function Definition

The running time of Program is determined
by the time required to merge the two children of the root (line 13)
since the rest of the work in `DequeueMin` can be done in constant time.
Consider the running time to delete the root of a leftist heap *T*
with *n* internal nodes.
The running time to merge the left and right subtrees of *T*

where and are the null path lengths of the left and right
subtrees *T*, respectively.
In the worst case, and .
If we assume that ,
the running time for `DequeueMin` is .

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.