HEAPS AND TRIES

Heaps

• Heaps are very similar to binary search tree (BST), they have two values – but unlike a BST, the children are always less than the parent (or more in a min tree).
• This means that your root node is always the biggest value in the whole tree.
• Because heaps aren’t so strict on the ordering, it’s quicker, O(log n), to insert data than it is into a sorted array.
• It’s also quicker on average to insert into than a BST, in both cases the insertion time comes down to the height of the tree but we can cheaply keep the heap balanced – no straight lines here!
• The downside is that heaps are slower for lookups, because you potentially have to look at every node in the tree.
• Finally, the killer feature – it’s really efficient to remove the root node.

How does it work?

• Heaps are typically stored in an array. Because it’s a binary tree you can quickly calculate a node’s children based on its index.
• Downside is you need to pre-allocate memory, and either have to set a max size or use a dynamic array data structure that will grow as needed.
• Adding to the heap has cool names like “up-heap”, “bubble up”, “trickle up”.
  • Add your node to the bottom level (easy in an array, just shove it in the first open value).
  • If the new node is less than its parent, swap and repeat.
• Extraction, downheap, trickle-down, bubble-down, etc.
  • Move the last filled value in the array to 0.
  • If this node is greater than one of its children, swap and repeat.

When to use?

• When you need to quickly insert data, and you only care about the min or max value.
• Don’t use a heap when you need to search for arbitrary values.
• Priority Queues (BFS).

Tries

• Tries, (technically) pronounced “tree” as in retrieval, aka digital tree, (compressed) radix tree, prefix tree.
• They are specialized tree where the nodes don’t matter.
• Instead, the “key” or “value” or “payload” is associated with the edges, and the nodes just exist for convenience.
• The true values in the tree only exist on the leaves, and siblings share what is called a common prefix.

When to use?

• Fast insert, fast and efficient sorting, lots of duplicated data…like in the bowels of search engines, or spell checkers/autocomplete.

sumber :

-https://www.google.com/imgres?imgurl=https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2F3%2F38%2FMax-Heap.svg%2F1200px-Max-Heap.svg.png&imgrefurl=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FHeap_(data_structure)&tbnid=J4YSnrROJmGmNM&vet=12ahUKEwiv_Ortw7DpAhUX-DgGHd21Bp0QMygAegUIARDwAQ..i&docid=rnX729SSQ2XDWM&w=1200&h=889&q=heaps%20and%20tries%20data%20structure&ved=2ahUKEwiv_Ortw7DpAhUX-DgGHd21Bp0QMygAegUIARDwAQ

-https://www.google.com/imgres?imgurl=https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2Fb%2Fbe%2FTrie_example.svg%2F1200px-Trie_example.svg.png&imgrefurl=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FTrie&tbnid=34jkA_88J_LiRM&vet=12ahUKEwiv_Ortw7DpAhUX-DgGHd21Bp0QMygBegUIARDyAQ..i&docid=RbU6Xb8ttbB0dM&w=1200&h=1125&q=heaps%20and%20tries%20data%20structure&ved=2ahUKEwiv_Ortw7DpAhUX-DgGHd21Bp0QMygBegUIARDyAQ

-https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=2ahUKEwjmo9-kw7DpAhXTyzgGHUjGARgQFjABegQIChAE&url=https%3A%2F%2Fwww.codingblocks.net%2Fpodcast%2Fdata-structures-heaps-and-tries%2F&usg=AOvVaw0HWcT7p7_a9bJ-BaOAaqyC