Heap (Max And Min) & Tries

Mei 13, 2020

Heap

Heap is a Tree Type data structure that has a complete set of nodes. Heaps are used in store array. What so special about Heaps is that every time we inserted value to it, it used its own Algorithm to sort itself and the way of indexing them is through left to right nodes in every level. You can access a parent of the node by dividing their index by 2.

Types of Heap

A. Max Heap

In Max Heap Binary Tree, The parent of the node child holds a value that is greater than its child value. The Max Value of the Tree is located at the Root of the tree.

B. Min Heap

In Max Heap Binary Tree, The parent of the node child holds a value that is smaller than its child value. The Min Value of the Tree is located at the Root of the tree.

Min Max Heap

C. Min Max Heap

Min Max Heap is a special case of Heap. It lets you build a tree structure that has an alternating structure where odd heights of the tree prioritize minimum value while the even heights prioritize maximum value. In which case, it is uncertain whether if the root of the tree has the smallest value of the tree.

Min Max Heap

Insertion And Deletion Method

Insertion and deletion method is used to insert and delete nodes from the tree. These methods require several conditions that are needed in order to insertion and deletion, let's take an example of this in Min Heap.

Let's say we wanted to insert the following values: 20 30 10

First, assign the very first node of the Min Heap Tree.

The 20 value now is the root of the Min Heap Tree and is the first index of the tree.

now let's continue by inserting the next value, 30.

As we can see, then tree prioritizes on inserting the tree node to the next index of the tree, which is the leftmost position of each height. Because this is a Min Heap tree, an if statement is called to check if the new node is smaller than its parent's node. In this case, 30 is greater than it's parent, so the algorithm decides that the newly inserted 30 node is already at the correct place.

Now let's insert the last value, 10.

the same process also happens like last time, but this time, because the newly "10" node has a smaller value than its parent (20), these values then are swapped.

Now that the tree has completed, let's try to do a deletion method.

For this case, let's try deleting the 10 nodes. When we delete the root node of tree, we will change the lastly added node to become the root of the tree. In this case, the 20 node will become the new root of the tree.

And in this case, we will rebalance the tree by heapfying the tree. But in this case, tree is already balanced as the new root "20" is the smallest node in this tree.

Tries

Trie or Tries is a Tree Type that that contains multiple nodes that make searching easier. Trie data structure are commonly used in autocorrect or autocomplete in browsers. Each node has a value in them and also a boolean value, pointing if a node in which case is the leaf of the node, or rather the end of the node.