Heap Data Structure

Heap data structure is a tree-based structure made up of nodes arranged in specific order where
the tree is a complete binary tree. Additionally, it a balanced binary tree in which the root node is
compared with its children. With heap the root node keys are compared with their children; for
example, if x has child node y, then the format shall be;

Operations of Heap Data Structure

Heap Data Structure Operations are of several types. Some operations of heap are outline below;

 Heapify
Heapify is a process of creating a heap from an array by rearranging values of heap trees to
manage heap structure after performing operation such as insertion and deletion. Once the
operation is done, the heap tree is re-arranged the tree to return the final outcome for
heap property

 Insertion
With insertion of heap, new element or value is added to the end of the heap first then it
will be rearranged to it correct position as the heap property follows the bottom-up
approach.

 Deletion
Deletion is done from the last node in a heap. With deletion, a particular element will be
deleted by the last node in a heap. After deletion, the heapify operation is used to
rearrange the heap tree.

 Peek
To check or find the most prior element in the heap. It returns and deletes the minimum or
maximum value in min-heap and max-heap, respectively.

Hashing
Hashing is a popular technique for storing and retrieving data as fast as possible. It is a procedure to
change a range of key qualities into a range of records of an array. It maps large amounts of
information to a smaller table with the help of a hashing function. It is also known as Hashing
Algorithm or Message Digest Function. The main reason for hashing is to give optimal results as it
performs optimal searches. It refresh and recover any information section in a steady time. Hashing
is used in databases to enable the recovery of things more rapidly and also used in encryption and
decryption of advanced and digital signatures.
How Hashing Works in a Data Structure

A fixed procedure changes over a key to a hash key and is known as a Hash Function. This
function takes a key and guides it to an estimation of a specific length which is known as a
Hash Value or Hash. This Hash Value is the real string of characters, yet it is typically slightly
small than the original one. It moves the computerized or digital signature and afterward,
both hash value and signature are sent to the beneficiary. The recipient utilizes a similar
hash capacity to produce the hash value and afterward contrasts it to the message In the
event that the hash value is the same, the message is transmitted without mistakes

Hashing Algorithm
The core of hashing is the hashing algorithm. Firstly, the data is partitioned into different blocks
before the hash value is computed. The reason for the portioning is that hash function takes in
information at a fixed-length and these fixed-length represent the length of the ‘data blocks.’ The
choice of size of the data blocks depends on the scenario where the algorithm will be applied.
Padding is used to isolate the whole message into fixed-size information squares or data blocks to
ensure the product of various blocks adds up to a complete message. According to the Avalanche
effect, each data blocks is processed in turn with the output from subsequent blocks serving as an
input to preceding block. A slightest change in a bit in the message can change the whole hash
value. Some examples of Hashing Algorithms are: Message Digest (MD) Algorithm, Secure Hash
Algorithm (SHA), RACE Integrity Primitives Evaluation Message Digest (RIPEMD), Whirlpool and RSA

Basic Operations of Hashing

HashTable: This operation is for creating a new hash table.

Delete: This operation is for deleting a particular key-value pair from the hash table

Get: This operation is used for searching a key in the hash table and returning the corresponding
value associated with the key.

Put: This operation is used to insert a new key-value pair inside the hash table.

DeleteHashTable: This operation is for deleting the hash table

Hashing Components

Hash Function It converts a given big value to a small practical integer value. The mapped integer
value is used as an index in hash table. Simply, hash function is used to transform a given key into a
specific slot index. Its main job is to map each and every possible key into a unique slot index. If all
keys are mapped into unique slot indexes, then the hash function can be referred to as a perfect
hash function.
Hash Table It is generally an array that stores pointers to records corresponding to a given value. A
hash table has NIL if no existing number has hash function value equal to the index for the entry. It
has an additional functionality such that a collection of data is stored in such a way that it is easy to
find those items later if required and this ensures efficient searching of an element.

Collision Handling Since a hash function gets us a small number for a key which is a big integer or
string, there is the possibility that two keys result in the same value. The situation where a newly
inserted key maps to an already occupied slot in the hash table is called collision and must be
handled using some collision handling technique

Hash Table

Hash Table is a table for storing all the values of the hash code used while storing the keys and their
corresponding data element values using hashing techniques. The hash table stores hash codes
which are generated by using the hash function. Hashing is the mechanism that enables the
identification of all the objects uniquely within the set of groups of objects.

Working of Hash Table

1. Indexing of the array ensure faster data access, that is, the hash table internally use the array to
store all the values while the unique indexing created by the hash tables acts as the indexing of the
array. This makes it possible to know the exact location of a stored value using its key.

2. This data structure stores all the values of the array or simply any other list or group of elements
along with its keys. This keys act as an index for referencing and storing of data. Whenever the key
or index becomes very big, the hash code reduces the key length by using a hash function.

3. The use of hash function must be chosen properly based on the fact that the resulting storage of
elements will be distributed uniformly across the hash table. This ensures that there is no clustering
of data at a single place in hash table. Moreover, the hash function should be very easy and simple
for calculation as increasing its complexity will increase the storage requirement as well as the
computations required.

4. Collision prevention technique must be used as it is common that a good hash function will be
chosen for hashing and may result in more than one value being mapped to the same hash value.
There are a lot of collision detection and resolution techniques such as open hashing also known as
separate chaining, linear probing or closed hashing, quadratic probing or double hashing.

Applications of Hash Tables and Hashing Technique

There are lots of algorithms that make use of hash tables to make computing faster. Hashing is used
in various ways such as –
a) Database Indexing: The disk-based data structures involve the usage of hash tables.

b) Associative arrays: In-memory tables implementation involves the usage of hash tables for
storing complicated or arbitrary strings as index implementing associative arrays in it.
c) Caches: auxiliary data tables implement hash tables which increase the speed of accessing the
data.

d) Object Representation: The programming languages that are dynamic in nature such as Perl,
ruby, JavaScript or python make the use of hash tables for storing objects.

Introduction to Recursion
A function that calls itself is referred to as Recursive function. That is the function gets invoke
repeatedly. Recursion has a problem-solving capacity where it divides the larger problems into
simple tasks and work them out individually to follow an individual sequence. Recursion executes a
specific part with the base function itself.

The general syntax of the recursive function in C++ is given as:

return type function name([arguments])

{
Body of the statements; function name ([actual arguments])
// recursive function
}

How Recursive Functions are Stored in the Memory

Recursion uses more memory, because the recursive function adds to the stack with each recursive
call, and keeps the values there until the call is finished.
The recursive function uses LIFO (LAST IN FIRST OUT) Structure just like the stack data structure

The Base Condition in Recursion

In a recursive program, the solution to the base case is provided and the solution to the bigger
problem is expressed in terms of smaller problems. In the example below, we defined a base case
of a < = 1. The larger value of a number can be solved by converting it into a smaller one till the
base case is reached.

int factVal(int a)
{
if (a < = 1) // base case
return 1;
else return a*factVal( a - 1);
}

How Problem are Solved Using Recursion

The main idea of recursion is to represent a problem in one or more smaller problems, and add one
or more base conditions that stop the recursion. For example, we compute factorial n if we know
the factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0. If we don’t
define a base case, then the stack overflow problem may arise.

Memory Allocation for Different Function Calls in Recursion

When any function is called from main(), the memory is allocated to it on the stack. When a
recursive function calls itself, the memory for a called function is allocated on top of memory
allocated to the calling function and a different copy of local variables is created for each function
call. When the base case is reached, the function returns its value to the function by whom it is
called and memory is de-allocated and the process continues.

Let us take the example of how recursion works by taking a simple function. // A C++ program to
demonstrate working of recursion

#include
using namespace std;
void printFuntime(int testVal)
{
f (testVal < 1)
return;
else {
cout << testVal << " ";
printFuntime(testVal - 1);
cout << testVal << " ";
return; } }

// Driver Code
int main()
{
int testVal = 3;
printFuntime(testVal);
}

Basic Understanding of Recursion

Write a program to find the Fibonacci series of n where n > 2

Mathematical Equation:
n if n == 0, n == 1;
fib(n) = fib(n-1) + fib(n-2) otherwise;

Recurrence Relation:
T(n) = T(n-1) + T(n-2) + O(1)

RECURSION AND BACKTRACKING

Recursion has a problem-solving capacity where it divides the larger problems into simple tasks and
work them out individually to follow an individual sequence. Recursion executes a specific part with
the base function itself. This session explained the visualization and the memory usage of recursion