# Heap and Trie in Data Structure

Mentor: Shailendra Chauhan
Duration : 00:05:00

## What is a Heap in Data Structures?

A heap is a data structure that consists of a complete binary tree. In a complete binary tree, all levels are filled except for the last, which may or may not be filled. A complete binary tree fills its elements from left to right.

## Types of Heap Data Structure

There are two primary types of heap data structures:

1. Max Heap
2. Min Heap

### Max Heap

A node is always larger than its child nodes, and the root node has the largest key among all nodes.

### Min Heap

A node is always smaller than its child node(s), and the root node's key is the smallest of all nodes.

## Heap Operations in Data Structures

Following are the Heap Operations in Data Structures:

• Heapify: Heapify creates a heap from an array.
• Insertion: Add an element to an existing heap.
• Deletion: Deletion is the process of removing the top element in a heap or the highest priority element.
• Peek: Find the heap's most prior element.
• Extract-Max/Min: Extract-Max returns the node with the highest value after removing it from the Max Heap, whereas Extract-Min returns the node with the lowest value after removing it from the Min Heap.

## Usages of Heap

• Dijkstra's Algorithms
• Heap Sort Algorithms

## Applications of the Heap

• Priority Queues: Elements are dequeued according to their priority, and heaps are frequently used for efficient insertions and removals.
• Graph Algorithms: Heap permits efficient Dijkstra's and Prim's algorithms by storing vertices/edges according to distance/weight.
• Sorting: Heap sort removes the largest element iteratively, sorting using heap construction.
• Memory Management: In C/C++, heaps manage dynamic memory by keeping track of free and allocated blocks.
• Event-driven Simulation: The heap in event simulation keeps events for efficient processes.

## What is a Trie?

A trie is a tree-based data structure that holds a collection of strings. The word trie derives from the verb reTRIEval, which means to find or obtain. If two strings share a prefix, they have the same ancestor in the trie. It stores a longer string and performs efficient searches on it.

## Need of Trie Data Structure

• Trie is used to store and retrieve data.
• Trie is more efficient than HashTable.
• Trie allows Prefix-based searching.

## Trie Data Structure Properties

• Trie has an empty root node that relates to other nodes.
• Nodes represent strings, whereas edges represent characters.
• Nodes contain hashmaps or arrays of pointers.
• The index identifies a character, whereas the flag indicates the end of a string.
• Alphabets, numerals, and special characters may all be present.
• 26 pointers are required for each node (a-z).
• The path from root to node represents a word or string.

## Working of Trie Data Structure

• Trie begins with an empty root node.
• Characters from a string are inserted one at a time, producing new nodes as needed.
• Each node represents a character, and edges connect them to other characters.
• Searching entails scanning nodes based on an input string and checking for existence.
• Trie, which enables for efficient prefix-based searching, is often used in autocomplete and dictionary applications.

## Basic Operations on the Trie Data Structure

The following are the basic operations of the Trie data structure:

• Insertion
• Search
• Deletion

### Insertion

Insertion is the process of adding a new string to the Trie by constructing nodes for each character that do not already exist and marking the last node to signal the string's end.

### Search

Determines whether a given string exists in the Trie by traversing the nodes based on the string's characters and ensuring that the string finishes at a valid node.

### Deletion

Removes a string from the Trie by traversing the nodes corresponding to the string's characters and eliminating them, optionally pruning unneeded nodes to ensure Trie's structural integrity.

## Applications of the Trie Data Structure

• Autocomplete: Autocomplete is powered by Trie, which suggests words as you type.
• Spell Checkers: Trie provides suggestions for misspelled words.
• Longest Prefix Matching: A trie-based technique improves network routing for IP addresses.

## Advantages of the Trie Data Structure

• Trie has O(l) time complexity for input and search, where l represents word length.
• Faster than hash tables or binary search trees.
• Allows alphabetical filtering and printing.
• Each key requires a fixed amount of space, hence it takes up less space than BST.
• Efficient for prefix search and longest prefix match.
• Faster than hash tables for small keys.
• In contrast to the pseudorandom order of hash tables, it allows for ordered iteration.
• The time complexity of deletion is O(l), where l is the length of a word.

## Disadvantages of the Trie Data Structure

• Due to the large number of node pointers, Trie consumes a lot of memory.
• Each node can have a large number of pointers, up to characters in the worst-case scenario.
• Efficient hash tables have an O(1) lookup time, which is quicker than Trie's O(l) lookup, where l is the string length.
Still have some questions? Let's discuss.