Heap and Tries

Heaps And Tries, both are a data structures algorithm concept



In this blog I will be summarizing :

• Heap Concept
• Min Heap 
• Max Heap
• Min-Max Heap
• Heap Applications
• Tries Concept
• Tries Applications

Heap is a complete binary tree which impliments the "heap" property.

Heap property ? 

Min Heap and Max Heap

Min Heap means every node's element is smaller than its children's

Max Heap means every node's element is larger than its children's

Heap Applications:

- Priority Queue 

  - Selection Algorithms

  - Dijkstra's Algorithm (finding shortest path in graph)

  - Prim Algorithm (finding minimum spanning tree)

- Heap Sort

We can also imply heap into arrays such as :

Formula (x) stands for a node's position :

Parent(x)=x/2

Left Child(x)=2*x

Right Child(x)=2*x+1

UpHeap, is a process that swaps values between current node and it's parents while it doesn't satisfy it's heap's property(min/max heap).

Insertion in Min Heap

UpHeap

Deletion in Min Heap

Delete Node 7

Replace 7 with the last element

UpHeap

Insertion and deletion in max heap have the same algortihm, the difference is in it's comparator (min/max heap)

Min-Max Heap is a complete binary tree which implements both min and max heap

The smallesst element is located at the root, 

the largest element is located in one of the root's child (right/left) 

Upheap min-max heap

• If new node is on a min level
• if new node's parent is smaller than it, upheapmax from its parent
• Else upheapmin from the new node
• If the new nod is on a max level
• if new node's parent is larger than it then swap their value and upheapmin from its pareng
• else upheapmax from the new node

Upheapmin in upheap min-max heap

Compare current node's value with its grand parent's value. While current node's value is smaller than it's grandparent's value, swap their values.

Upheapmax in upheap min-max heap

Compare current node's value with its grand parent's value. While current node's value is larger than it's grandparent's value, swap their values

min max heap insert value 50

Upheapmin, 50 is larger than its parent(28), upheadmax

Upheadmax, 50 is larger than its grand parent(35) so they swap value

Deletion in min max heap

• Replaceroot with the last element in heap
• decrease the number of element in heap
• downheapmin from root

Deletion  of the largest element

• Replace either left or right child of rood (larger one) with the last element in heap
• Decrease the number of element in heap
• Down heapmax from the node

Downheap min/max in min-max heap

The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap.

•Downheapmin

•Let m is the smallest element in current node’s children and grandchildren (if any).

•If m is grandchildren of current node then

•If m is smaller than current node then

•Swap their value

•If m is larger than its parent then swap their value

•Continue downheapmin from m

•If m is children of current node then

•If m is smaller than current node then

•Swap their value

•Downheapmax is the same except the comparators is reversed.

Min Max Heap delete Max

Replace The value with the last node

Downheapmax

Downheapmax

because 14 parents is larger than 14., swap

done

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

Tries Example

We can see that this tree holds associative data between strings

• ALGO
• API
• BOM
• BOSAN
• BOR

Those are the material I learned from data structures at 12/05/2020 (dd/mm/yyyy), sorry if there are mistakes made in this summary. thanks for reading :)