Binary heap in data structures algorithms.pdf

Binary heap

1. Shri Ramswaroop
Memorial University
Deva Road , Barabanki
Name : Aayush Tiwari
Roll No: 202310101050052
Course: MCA Sem: 2nd Sem
Subject: Data Structures and Algorithms
Submitted To: Mr. Harendra Singh Kharwal

2. TOPIC
BINARY HEAP TREE

3. Binary Heap Tree:
A Binary Heap is a complete Binary Tree which is used
to store data efficiently to get the max or min element
based on its structure.
A Binary Heap is either Min Heap or Max Heap. In a Min
Binary Heap, the key at the root must be minimum
among all keys present in Binary Heap. The same
property must be recursively true for all nodes in Binary
Tree. Max Binary Heap is similar to MinHeap.

4. Complete Binary Tree
A complete binary tree is a binary tree in which
every level, except possibly the last, is completely
filled, and all nodes in the last level are as far left
as possible

5. Types of Heap
There are two types of heap data structures
Max Heap 1.
Min Heap2.
1.Max Heap
In a Max Heap, the parent node is always greater than or
equal to its child nodes
2.Min Heap
In a Min Heap, the parent node is less than or equal to
its child nodes.

7. Heap Tree Representation

8. Operations on Binary Heap:
create-heap: create an empty heap
heapify: create a heap out of given array of elements
find-max or find-min: find a maximum item of a max-heap, or a minimum item of a min-heap
insert. adding a new key to the heap
delete-max or delete-min: removing the root node of a max- or min-heap, respectively
size: return the number of items in the heap.
merge (union): joining two heaps to form a valid new heap containing all the elements of both,
preserving the original heaps

9. Application of Binary Heap
Heapsort: One of the best sorting methods being in-place and with no quadratic worst-
case scenarios.
Finding the min, max, both the min and max, median, or even the k-th largest element can
be done in linear time using heaps.
Priority Queue:: Priority queues can be efficiently implemented using Binary Heap
because it supports insert(), delete() and extractmax(), decreaseKey() operations in
O(logn) time.
Graph algorithms like Prim's Algorithm and Dijkstra's algorithm.

10. Thank
you