About Priority Queue

Stack: FILO (first in, last out) 1

• Stored in computer RAM
• stack grows and shrinks as functions push and pop local variables; Variables are allocated and freed automatically .
• CPU manage the memory, reading from and writing to stack variables is very fast

Heap 1

• Stored in computer RAM
• heap variables are essentially global in scope.
• Heap memory is slightly slower to be read from and written to, because one has to use pointers to access memory on the heap.
• If we need variables like arrays and structs that can change size dynamically, then we will likely need to allocate them on the heap.

queue : FIFO

stack : FILO (first in, last out)

Priority Queue

• The case

  • We collect a set of items, then process the one with the largest key, then perhaps collect more items, then process the one with the current largest key.

  • a collection in which items can be added at any time, but the only item that can be removed is the one with the highest priority.

  • The implementations

  • unordered array/linked-list:

    • To insert: push in the stack. O(1)
    • To remove the max: exchange the MAX with the item at the end, and then delete that one. o(n)

  • ordered array/linked-list:

    • for insert to move larger entries on the right position,thus keeping the keys in the order array. o(n)
    • The MAX is always at the end. O(1)

  • binary heap 2

    • a binary tree is heap-ordered if the key in each node >= the keys in the node's two children 3.
    • To insert: exchanging the node with its parent to restore the heap condition

    • To remove:

      • take the key off the top;
      • put the item at the end of the heap to the top,
      • and then sink through the heap with the key to restore the heap condition

    • In a heap, the highest (or lowest) priority item is always stored at the root, hence the name "heap". A heap is not a sorted structure and can be regarded as partially ordered . There is no particular relationship among ndoes on any given level, even among the siblings 4.

    • A heap is useful data structure when we need to remove the object with the highest (or lowest) priority.

    • O(logN)