priority queue notes

Priority Queue

Implementing a priority queue using a Scala ArrayBuffer

Like a normal queue except each element has a "priority" attached to it

There are several ways-- we will look at Array and Heap Ordered Tree (HOT)

=====

Two invariants-- shape invariant and max or min-heap invariant (these are for a binary tree NOT a binary search tree)
Shape invariant-- insists that all levels are full except for bottom level
Max-heap-- insists that the parent is at least as big as the children (min = at least as small)

just make sure max or min heap holds all the way down-- parent node is greater than both of its child nodes

How to queue-- put it in the last spot and then "sift" all the way up to restore the invariant

How to dequeue-- removing the root node breaks the tree, so swap it with the last element in the queue and then sift DOWN to restore the invariant.
When sifting down, swap with the higher priority element of the two children

=====

How do we implement this?  How do we get the mutable ArrayBuffer to act like the tree?
The ArrayBuffer must hold all the elements and the highest priority element must be the first element in the queue
They can come in random order but they must be placed in the right spot once they show up

Once all elements are queued we will dequeue and insert a new one

We can calculate where parents/children are using the indices

i left = 2i+1
i right = 2i+2
i parent = floor(i-1)/2
( we don't need floor because of int math so it can just be (i-1)/2 )

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

HW 9:
https://gyazo.com/ab3e5f18bb10a49e48a9061752896199
and then use x.toString

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

Queue with Heap is a minheap

When we dequeue a heap tree we split the two trees so we need a way to merge them

HW 10:
https://gyazo.com/54f40d25696eab899a2867bb3627b797    (case class H)
https://gyazo.com/3c8634a5d965ca75824502f72156c65f    (size and merge and stuff)