Heap and Hash : An Overview

Master the fundamentals of Heaps and Hashing

Heap:

1. Introduction to Heap:

A heap is a tree-based data structure that utilizes a complete binary tree for its creation and implementation.

2. Properties of a Heap:

• A heap is a complete binary tree.
• The root node is located at H[0].
• H[(i-1)/2] gives the parent node.
• H[(2*i)+1] gives the left child node.
• H[(2*i)+2] gives the right child node.

3. Types of Heap:

There are mainly two types of heaps:

• Max-Heap: In this type of heap, the value of the parent node is always greater than its children. This property is recursively true for all sub-trees in the binary tree. The root node contains the highest value in the heap.

Min-Heap: In this type of heap, the value of the parent node is always less than its children. This property is recursively true for all subtrees in the binary tree. The root node contains the minimum value in the heap.

4. Insertion in a Heap

Inserting elements into a heap is straightforward, but it’s crucial to maintain the heap property. The following algorithm outlines the insertion process:

1. Increase the size of the heap by 1 to accommodate the new element.
2. Insert the element at the end of the heap to maintain the complete binary tree structure.
3. Compare the inserted element with its parent:

• For a Max-Heap, swap if the parent’s value is less than the inserted element.
• For a Min-Heap, swap if the parent’s value is greater than the inserted element.

1. Continue comparing and swapping until the heap property is restored.

5. Deletion from a Heap

When deleting elements from a heap, only the root node can be removed. The following steps outline the deletion process:

1. Shift the entire tree upwards.
2. Remove the root node and replace it with the last element in the heap.
3. Compare the new root with its children:

• For a Min-Heap, if the root is greater than any of its children, replace it with the child of the smallest value.
• For a Max-Heap, if the root is smaller than any of its children, replace it with the child of the greatest value.

1. Continue comparing and swapping until the heap property is restored.

6. Heap Sort

Heap sort utilizes the deletion process of a heap:

• Max-Heap: Deleted nodes are in decreasing order, resulting in a sorted array in decreasing order.
• Min-Heap: Deleted nodes are in increasing order, resulting in a sorted array in increasing order.

Hashing Techniques:

Hashing is a technique for mapping keys and values into a hash table using a hash function, enabling faster access to elements. The efficiency of this mapping relies on the effectiveness of the hash function used.

Types of Hash Functions:

1. Ideal Hash Function: ( h(x) = x ), where ( x ) is the element to be mapped.
2. Standard Modulus Function: ( h(x) = x \% 10 ), where ( x ) is the element to be mapped.
3. Custom Random Function: ( h(x) = \text{} ).

What are Collisions?

A collision occurs in a hash table when more than one key is mapped to a specific index. Since a hash table allows storing only one element per index, a newly inserted key mapped to an already occupied index results in a collision.

Resolving Collisions in Hashing:

There are two main methods to resolve collisions when mapping elements into a hash table:

1. Open Hashing:

• In open hashing, additional storage space is used along with the hash table. This method employs an array of linked lists to resolve collisions.
• The element to be mapped is stored in a linked list external to the hash table memory, allowing values to be stored outside the hash table.
• This technique uses chaining to resolve collisions, where all key-value pairs mapping to the same index are stored in the linked list at that index. Example: Consider the following elements: 9, 24, 37, 58, 99, 114, 109, 64, 88 Hash Function: ( h(x) = x \% 10 ).

Initial Hash Table:

Function Values:

h(9) = 9%10 = 9

h(24) = 24 %10 = 4

h(37) = 37%10 = 7

h(99) = 99%10 =9

h(58) = 58%10=8

h(114) = 114 %10 =4

h(109) = 109%10=9

h(64) = 64 % 10 =4

h(88) = 88 %10 =8

Final Table after inserting values:

2. Closed Hashing:

1. 1.Linear Probing:
2. Consider the following example elements: 36, 20, 25, 43, 65, 74, 33, 87

Initial Hash Table:

1. Modified Hash Function:
2. Initially we use the standard modulus function to insert or map values into the hash table.
3. When a collision occurs while mapping in the table we use the modified hash function iteratively until an empty index or slot is found.
4. h’(x) = [h(x) + f(i)] %10 where f(i) = i; i = 0, 1, 2, 3, 4, 5…
5. Hash Functional Values: 36, 20, 25, 43, 65, 74, 33, 99
6. h’(36)=6
7. h’(20)=0
8. h’(25)=5
9. h’(43)=3
10. h’(65)=5 (C)
11. h’(74)=4
12. h’(33)=3(C) h’(87)=[C]

Table after insertion:

2. Quadratic Probing:

Consider an example:

36, 20, 25, 43, 65, 74, 33,99

Initial Hash Table:

Modified Hash Function:

• Initially we use the standard modulus function to insert or map values into the hash table.
• When a collision occurs while mapping in the table we use the modified hash function iteratively until an empty index or slot is found.
• h’(x) = [h(x) + f(i)] %10 where f(i) = i²; i = 0, 1, 2, 3, 4, 5…

Hash Functional Values:

h’(36)= 6

h’(20)= 0

h’(25)= 5

h’(43)= 3

h’(65)= 9 (C)

h’(74)= 4

h’(33)= 7(C) h’(99) = 1 (C)

Table after insertion:

3. Double Hashing:

Consider an example:

5, 25, 15, 35,95

Initial Hash Table:

Modified Hash Function:

• Initially we use the standard modulus function to insert or map values into the hash table.
• When a collision occurs while mapping in the table we use the modified hash function iteratively until an empty index or slot is found.
• h1(x) = x % 10
• h2(x) = R — ( x % R) where R = closest prime number less than size of hash table.
• h’(x) = [h1(x) + i*h2(x)] %10 where f(i) = i; i = 0, 1, 2, 3, 4, 5…

Hash Functional Values:

h’(5)=5

h’(25)=8

h’(15)=1

h’(35)=2

h’(95)=4

Table after insertion:

Read More…

Understanding SQL Joins: A Comprehensive Guide – https://kamleshsingad.com/understanding-sql-joins-a-comprehensive-guide/

Top 10 SQL Programming Tips for Beginners – https://kamleshsingad.com/top-10-sql-programming-tips-for-beginners/

Introduction to SQL Programming: A Beginner’s Guide – https://kamleshsingad.com/introduction-to-sql-programming-a-beginners-guide/