CPSC 2120 - DAY 13
JUNE 1, 2016

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

BINARY HEAPS
------------

An example of a complete tree. 

Insert
Delete

Allows efficient inserts and deletes of the minimum value (minheap) or 
maximum value (maxheap)

One array implementation of a binary tree

Root of tree is at element 1 of the array

node 2i, 2i+1

If node is on element 5, parent floor(i/2)

*** EQUALITY IS ALLOWED ***

if the value of the node is greater than or equal to its children, the highest
value would be at the root

The purpose of the heap is to have the largest or smallest at the root at all
time

all leaves are on the lowest two levels

nodes are added on the lowest level from left to right

insert at first avaliable space.

compare with would-be parent

move parents down until you find the right place

worst case O(log n) AKA height of tree (log n)

Delete a value:

remove value from the root


Order of complexity of Delete/insert is log n

Leftist Heap

good for merging two heaps

null path length - the shortest distance between from that node to a descendant
with 0 or 1 child.  If a node is null, it's null path length is -l