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