Priority Queue

What is priority queue?

A data structure for maintaining items or elements in a queue of priorities, which is usually implemented using an array. A queue of this nature helps to insert every item with an assigned priority and these inserted items could be deleted if required.


Minimum number of queues needed to implement the priority queue?
Two. One queue is used for actual storing of data and another for storing priorities.

• With priority queue it's possible to insert items then remove max or min.
• Simple implementation is to have array / linked list. And either keeping elements sorted or iterate all items when removing.
• This makes some operations cost N.
• A better implementation is with a binary heap / complete binary tree / a tree that is perfectly balanced except the bottom row. This makes priority queue take log n time.

Implemented as Binary heap

• Binary heap can be implemented using an array where the root is a[0], 1st level is a[1] and a[2] and so on.
• Swim Operation - if a child is larger than parent, switch with parents until the root of the tree.
• Insert is simple. Add to the end of the array and swim if needed.
• Sink is the opposite - if parent becomes smaller - exchange with larger of two children.
• To remove item, return head, replace head with last item in the array and sink
• It's better to make data immutable by copying data to local instance variable.

Immutable

• Ensures data/keys don't change while they are in the collection.
• Disadvantage is doubling the data.
• Classes should be as immutable as possible

Heapsort

• Construction - start from the leaves - ensure each sub tree is a correct heap
• Sortdown - Remove highest element and exchange with last element. Sink. Repeat until all elements are out of the heap
• array should now be sorted.
• Result: In place sort with NlogN cost in the worse case. Better than Quicksort quadratic time worse case.
• Cons: Not stable, poor use of cache memory.

Event driven simulation

• Using priority queue sorted by next collision.
• Main loop:
  • Pull next collision, advance time to that collision
  • Resolve collision
  • Calculate new collisions for the two participating particles

Symbol Table

• Storing key/value pairs
• Properly writing equals method
  • check for null
  • check if they are the same class
  • compare fields
• Simple implementation - linked list - every operation requires searching the list. Cost: N.
• Sorted array for keys and using binary search
• Ordered operations that we can allow: min(), max(), keys(min, max), select(index), floor(time).

Binary Search Tree implementation.

• Every node's key is:
  • Larger than all keys on the left subtree
  • Smaller than all keys on the right subtree
• To find a key, keep going down the tree with greater/right, less/left until getting to the place.
• To insert: similar to get, just insert where we stopped.
• Issue: key order affects the tree shape.
• Ordered Operations:
  • min: go to the left most tree
  • max: go to the right most tree
• Iterate:
  • In-order: add left, add self, add right
• Delete a node with no children - simple
• Delete min - promote right subtree if available to replace the min
• Hibbard Deletion - to delete a node:
  • if there are two children - find min from the right subtree. Delete the min, assign min to replace deleted node, with same left/right sub-trees.
• Over time the tree will get unbalanced and deletion will be sqrt(N)

 Source
https://github.com/mb-dev/mb-dev.github.io/blob/master/study-notes/algorithms/week4.md