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)
-