Heap & Tries

Heap

Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly.

1. Min Heap

-Each node’s element is smaller than its children’s element.

-It implies that the smallest element is located at the root of the tree.

-The largest element is located somewhere at one of the leaves node.

-Heap can be implemented using linked-list, but it is much easier to implement heap using array.

2. Max Heap

-Each node’s element is larger than its children’s element.

-It implies that the largest element is located at the root of the tree.

-Max-heap holds the same principle as min-heap and can be used to create priority queue which need to find the largest element instead of the smallest one.

*Example:

3. Min Max Heap

-The heap condition alternates between minimum and maximum level to level

-Each element on even/odd level are smaller than all its children (min-level).

-Each element on odd/even level are larger than all its children (max-level).

-The purpose of min-max heap is to allow us to find both the smallest and the largest element of the heap at the same time.

In Min Max Heap,

-The smallest element is located at the root.

-The largest element is located in one of the root’s child (either left/right child).

Tries

-Tries (prefix tree) is an ordered tree data structure that is used to store an associative array (usually strings)

-The term TRIE comes from word RETRIEVAL, because tries can find a single word in a dictionary with only a prefix of the word.