Implementation

• Simple Linked List


  Performing insertions at the front in O(1) and traversing the list, which requires O(N) time, to delete the minimum.
• Binary Search Tree 


  This gives an O(log N) average running time for both operations.
• Binary Search Tree Deletions


  Recall that the only element we ever delete is the minimum. Repeatedly removing a node that is in the left subtree would seem to hurt the balance of the tree by making the right subtree heavy. However, the right subtree is random. In the worst case, where the deleteMins have depleted the left subtree, the right subtree would have at most twice as many elements as it should. This adds only a small constant to its expected depth. Notice that the bound can be made into a worst-case bound by using a balanced tree; this protects one against bad insertion sequences.
• Using a search tree could be overkill because it supports a host of operations that are not required.
• The basic data structure we will use will not require links and will support both operations in O(log N) worst-case time. Insertion will actually take constant time on average, and our implementation will allow building a priority queue of N items in linear time, if no deletions intervene.