CPSC 2120 - DAY 18
JUNE 10, 2016

================================================================================

Priortiy Queues:
Binary Heap
Leftist Heap
Skew Heap



BINOMIAL QUEUES
---------------

A binary heap provices O(logn) inserts and O(logn) deletes but suffers from
O(nlogn) merges

A binomial queue offers O(logn) inserts and O(log n) deletes and O(logn) merges

Note, however, binomial queue inserts and deletes are more expensive than
binary heap inserts and deletes.

A Binomial Queue is a collection of heap-ordered trees known as a forest.
  Each tree is a binomial tree.  A recursive definition is:

 A binomial tree of height 0 is a one-node tree.
 A binomial tree, Bk, of height k is formed by attaching a binomial tree Bk−1 
 to the root of another binomial tree Bk−1 .


An empty tree is any tree you want it to be.

By checking the roots of all of the trees in the binary queue,
 you can determine the minimum value.  

finding the minimum value is logn
removing the value is a logn operation

Merging Binomial Queues

when doing an insert, you are merging with a B_0

TRAVELING SALESMAN PROBLEM
--------------------------

NP COMPLETE

Very hard to solve