Samenvatting AD1
Is voor het grootste deel in order van de hoofdstukken, maar niet helemaal
--> felt like starting w some datastructures
Heaps:
Use cases
Top K problems (min 10 elements of 10 list)n
Minheap maxheap
Dynamic data / streaming: quick insertions and deletes
Shortest path: keep track of only closest
Memory management: free list of memory blocks in RAM
Why it's better than just sorting a list for the first elements ^^
Operation Sorted List Heap (Priority Queue)
Build/Initial Setup O(N log N ) O(N )
Get Min/Max O(1) O(1)
Insert New Element O(N ) (must shift elements) O(log N )
Remove Min/Max O(N ) (must shift elements) O(log N )
Heapify: O(n)
= from-scheme-vector = bottom-up construeren met sift-down
--> de naïeve heapify van nlog(n) is gewoon alles inserten met sift
Visuele voorstelling: volledige binaire boom
MAAR! In realiteit is het een vector
,Adding shit:
Add to last part
Sift-up (swap with parent) until it's in the right place
gg
Deleting shit:
, Remove root
Put last element into root
Sift last element down (picking smallest to swap w always)
gg
Stack:
LIFO
push pop top
performantie beide vectorieel en linked list O(1)
--> kies op vlak van flexibiliteit vs memory
Queue:
FIFO
serve = pop (denk grocery store, ge served een customer)
enqueue = push
peek = top
performantie beide vectorieel en linked list O(1)
Priority Queue:
HPFO: highest priority first out
Dit kan gemaakt worden met positional list, sorted list, etc.
Maar op basis van heap is het beste --> enqueue/serve O(log n)
peek = highest prio element bekijken
proceduretype = combinatie input datatypes outputdatatypes
ascii: 48 --> 0
ascii: 65 --> A
ascii: 97 --> a
Is voor het grootste deel in order van de hoofdstukken, maar niet helemaal
--> felt like starting w some datastructures
Heaps:
Use cases
Top K problems (min 10 elements of 10 list)n
Minheap maxheap
Dynamic data / streaming: quick insertions and deletes
Shortest path: keep track of only closest
Memory management: free list of memory blocks in RAM
Why it's better than just sorting a list for the first elements ^^
Operation Sorted List Heap (Priority Queue)
Build/Initial Setup O(N log N ) O(N )
Get Min/Max O(1) O(1)
Insert New Element O(N ) (must shift elements) O(log N )
Remove Min/Max O(N ) (must shift elements) O(log N )
Heapify: O(n)
= from-scheme-vector = bottom-up construeren met sift-down
--> de naïeve heapify van nlog(n) is gewoon alles inserten met sift
Visuele voorstelling: volledige binaire boom
MAAR! In realiteit is het een vector
,Adding shit:
Add to last part
Sift-up (swap with parent) until it's in the right place
gg
Deleting shit:
, Remove root
Put last element into root
Sift last element down (picking smallest to swap w always)
gg
Stack:
LIFO
push pop top
performantie beide vectorieel en linked list O(1)
--> kies op vlak van flexibiliteit vs memory
Queue:
FIFO
serve = pop (denk grocery store, ge served een customer)
enqueue = push
peek = top
performantie beide vectorieel en linked list O(1)
Priority Queue:
HPFO: highest priority first out
Dit kan gemaakt worden met positional list, sorted list, etc.
Maar op basis van heap is het beste --> enqueue/serve O(log n)
peek = highest prio element bekijken
proceduretype = combinatie input datatypes outputdatatypes
ascii: 48 --> 0
ascii: 65 --> A
ascii: 97 --> a
