Skip to content

Commit 3184ae0

Browse files
nikitakapoor1919nikitakapoor1919
authored
Add Readme.md for Heap Data Structure (TheAlgorithms#2440)
1 parent 599278b commit 3184ae0

1 file changed

Lines changed: 128 additions & 0 deletions

File tree

‎DataStructures/Heaps/Readme.md‎

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
<b><h1 align=center> HEAP DATA STRUCTURE</h1></b>
2+
<p>A Heap is a special Tree-based data structure in which the tree is a complete binary tree.
3+
4+
## <h2>Complete Binary Tree</h2>
5+
<p>A complete binary tree is a binary tree
6+
in which all the levels except the last level, i.e., leaf node should be completely filled, and all the nodes should be left-justified.</p>
7+
8+
9+
```
10+
10
11+
/ \
12+
20 30
13+
/ \
14+
40 50
15+
16+
COMPLETE BINARY TREE
17+
```
18+
19+
20+
## <h2>Types of Heap</h2>
21+
<p>Generally, Heaps can be of two types:
22+
<br>
23+
<strong>Max-Heap:</strong> In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
24+
<br>
25+
<strong>Min-Heap:</strong> In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
26+
</p>
27+
28+
29+
30+
```
31+
10
32+
/ \
33+
20 30
34+
/ \ / \
35+
40 50 60 70
36+
37+
MIN HEAP
38+
```
39+
40+
```
41+
70
42+
/ \
43+
50 60
44+
/ \ / \
45+
40 30 10 20
46+
47+
MAX HEAP
48+
```
49+
50+
## <h2>Min Heap Construction Algorithm</h2>
51+
```
52+
Step 1 − Create a new node at the end of heap.
53+
Step 2 − Assign new value to the node.
54+
Step 3 − Compare the value of this child node with its parent.
55+
Step 4 − If value of parent is more than child, then swap them.
56+
Step 5 − Repeat step 3 & 4 until Heap property holds.
57+
```
58+
59+
```
60+
Add 15
61+
62+
10 10 10
63+
/ \ / \ / \
64+
20 30 ------> 20 30 ------> 20 15
65+
/ \ / \ / / \ /
66+
40 50 40 50 15 40 50 30
67+
68+
69+
```
70+
71+
## <h2>Min Heap Deletion Algorithm</h2>
72+
```
73+
Step 1 − Remove root node.
74+
Step 2 − Move the last element of last level to root.
75+
Step 3 − Compare the value of this child node with its parent.
76+
Step 4 − If value of parent is more than child, then swap them.
77+
Step 5 − Repeat step 3 & 4 until Heap property holds.
78+
```
79+
80+
```
81+
Delete 10
82+
83+
10 50 20 20
84+
/ \ / \ / \ / \
85+
20 30 ------> 20 30 ------> 50 30 ------> 40 30
86+
/ \ / / /
87+
40 50 40 40 50
88+
89+
90+
```
91+
92+
## <h2>Time Complexity (Min Heap)</h2>
93+
<table border=1>
94+
<tr>
95+
<th>Operations</th>
96+
<th>Sorted Array</th>
97+
<th>UnSorted Array</th>
98+
<th>Heap</th>
99+
</tr>
100+
<tr>
101+
<td>Add</td>
102+
<td>O(N)</td>
103+
<td>O(1)</td>
104+
<td>O(logN)</td>
105+
</tr>
106+
<tr>
107+
<td>Delete Minimum</td>
108+
<td>O(N)</td>
109+
<td>O(N)</td>
110+
<td>O(logN)</td>
111+
</tr>
112+
<tr>
113+
<td>Get Minimum</td>
114+
<td>O(1)</td>
115+
<td>O(N)</td>
116+
<td>O(1)</td>
117+
</tr>
118+
</table>
119+
120+
## <h2>Applications of Heap Data Structure</h2>
121+
122+
<p>
123+
<strong>Heapsort:</strong> Heapsort algorithm has limited uses because Quicksort is better in practice. Nevertheless, the Heap data structure itself is enormously used.
124+
125+
<strong>Priority Queues:</strong> Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in O(logn) time which is a O(n) operation in Binary Heap. Heap Implemented priority queues are used in Graph algorithms like Prim’s Algorithm and Dijkstra’s algorithm.
126+
127+
<strong>Order statistics:</strong> The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.
128+
</p>

0 commit comments

Comments
 (0)