Skip to content
  • Linkedin
  • Youtube
  • Pinterest
  • Home
  • Privacy Policy
  • About
  • Contact
Programmingoneonone

Programmingoneonone

Programmingoneonone is a website that publishes daily tutorials, methods, guides, and articles on IT, Education, and technology.

  • Home
  • Human Values
  • DSA
  • IoT Tutorials
  • Interview Questions and Answers
  • Toggle search form
heap in data structure

Heap in Data Structure

Posted on 5 June 202023 April 2023 By YASH PAL No Comments on Heap in Data Structure

In Data Structure a Heap is a Binary tree in which all levels have a maximum number of nodes except possibly the last level and in the last level all the nodes are to the left and the key in any node is greater than or equal to the keys in both children of the node.

The heap is also called a complete binary tree.

heap in data structure

here in the above tree root node has a maximum value and all the nodes have greater values in comparison to their both left and right child nodes. and in the last level, all the single nodes are on the left. so this is a heap.

Properties of Heap

Structure properties

All levels have a maximum number of nodes except possibly the last level
In the last level, all the nodes are to the left

Heap order properties

The key in any node N is greater than or equal to the keys in both children of N

Types of Heap in the data structure

Basically, the heap has two types max heap and min heap.

What is the Max heap?

In the max heap key in any node, N is greater than or equal to the keys in both children of node N.

heap in data structure

in the above heap, every node has a greater value in comparison to their left and child nodes. so this is a max heap.

What is Min heap

In the min-heap key in any node, N is smaller than or equal to the keys in both its children.

heap in data structure

in the above example, all the nodes have smaller values in comparison to their left and child nodes. so this is a min-heap.

Representation of Heap

as we know that the heap is a complete binary tree so it is easy to represent the heap using sequential memory location.

let’s say we have a heap of size n then

  • we store the root in an array at index 1.
  • the left child of node N at index 2i.
  • the right child of node n at index 2i + 1.
  • Parent of node at index floor(i/2)

if the value of 2i is greater than the size of heap n then the left child of the node does not exist and if the 2i + 1 is greater than the size of heap n then the right child of the node does not exist.

Here we have a heap of size 12.

heap in data structure

to represent this heap using an array first, we store 85 which is a root node at index 1 and 70, and 55 which is the left and right node of the root node at 2i and 2i + 1 locations.

heap in data structure

Applications of Heap

A heap is used to solve problems where the largest or smallest value has to be found. for finding the largest values we use the max heap and for finding the smallest value we use the min heap.

We also use the heap in the selection algorithm where we need to find the kth largest element. in this problem, we build a heap a then the root is deleted k times.

We use the heap to implement a priority queue because using the heap the insertion and deletion become the O(log n).

We also use to sort elements using a heap and this sorting algorithm is called a heap sort.

Program to implement Heap using Python.

class HeapEmptyError(Exception):
    pass

class Heap:

    def __init__(self, maxsize=10):
        self.a = [None] * maxsize
        self.n = 0
        self.a[0] = 99999
    def insert(self, value):
        self.n + 1
        self.a[self.n] = value
        self.restore_up(self.n)

    def restore_up(self, i):
        k = self.a[i]
        iparent = i // 2
        while self.a[iparent] < k:
            self.a[i] = self.a[iparent]
            i = iparent
            iparent = i // 2
            self.a[i] = k

    def delete_root(self):
        if self.n == 0:
            raise HeapEmptyError("Heap is empty")

        maxValue = self.a[1]
        self.a[1] = self.a[self.n]
        self.n -= 1
        self.restore_down(1)
        return maxValue

    def restore_down(self, i):
        k = self.a[i]
        lchild = 2 * i
        rchild = lchild + 1
        while rchild <= self.n:
            if k >= self.a[lchild] and k >= self.a[rchild]:
                self.a[i] = k
                return            else:
                if self.a[lchild] > self.a[rchild]:
                    self.a[i] = self.a[lchild]
                    i = lchild
                else:
                    self.a[i] = self.a[rchild]
                    i = rchild

            lchild = 2 * i
            rchild = lchild + 1
        if lchild == self.n and k < self.a[lchild]:
            self.a[i] = self.a[lchild]
            i = lchild
            self.a[i] = k

    def display(self):
        if self.n == 0:
            print("Heap is empty")
            return        print("Heap size = ", self.n)
        for i in range(1, self.n + 1):
            print(self.a[i], " ", end='')
        print()


#####################################
h = Heap(20)
while True:
    print("1. Insert")
    print("2. Delete root")
    print("3. Display")
    print("4. Exit")
    print("Enter your choice : ")
    choice = int(input("Enter your choice : "))

    if choice == 1:
        value = int(input("Enter the value to be inserted : "))
        h.insert(value)

    elif choice == 2:
        print("Maximum value is ", h.delete_root())
    elif choice == 3:
        h.display()
    elif choice == 4:
        break    else:
        print("Wrong choice")
Computer Science Tutorials, Data Structures Tutorials Tags:computer science, Data Structure

Post navigation

Previous Post: Deletion in Binary Search Tree
Next Post: Basics of C Programming

Related Tutorials

vi editing commands VI Editing Commands For Linux Computer Science Tutorials
modes of vi editor VI Editor in Linux Computer Science Tutorials
environment and path setting in linux Environment and Path Setting in Linux Computer Science Tutorials
hard and synbolic links in linux Hard links and Symbolic links Computer Science Tutorials
changing file access permissions Changing File Access Permissions in Linux Computer Science Tutorials
access permissions in linux Access permissions in Linux Computer Science Tutorials

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick your Subject

  • Internet of Things
  • Data Structures/Algorithms
  • Interview Preparation
  • Human Values
  • Java Interview Questions and Answers (2023)
    Thinking of becoming a Java developer? I must say it’s a good choice! Java is continuously named the most popular programming language. And the...

    Learn More “Java Interview Questions and Answers (2023)” »

  • Iot(Internet of things) in healthcare
    IoT in Healthcare
    IoMT (Internet of Medical Things) stands for devices that can collect and exchange data – either with users or other devices via the internet,...

    Learn More “IoT in Healthcare” »

  • four stages of iot solution for industry
    IoT for Industry
    In this post, we are going to learn about use cases of IoT for Industry and four stages for providing IoT solutions. Machine Diagnosis...

    Learn More “IoT for Industry” »

  • Iot for agricultural
    IoT in Agriculture
    IoT technology has realized smart wearables, connected devices, automated machines, and driverless cars. However, in agriculture, the IoT has brought the greatest impact. Amongst the challenges...

    Learn More “IoT in Agriculture” »

  • Iot for logistics
    IoT in Logistics and Supply Chain
    IoT applications for smart logistics and supply chain systems:  Logistics Fleet Tracking  To track the locations of the vehicles in real time, the vehicle...

    Learn More “IoT in Logistics and Supply Chain” »

  • Algorithms Tutorials
  • Basic Programming
  • C Programming Tutorials
  • C++ Tutorials
  • Compiler Design Tutorials
  • Computer Networks Tutorials
  • Computer Organization Tutorials
  • Computer Science Tutorials
  • Data Structures Tutorials
  • DBMS Tutorials
  • Developer Guide
  • Digital Communication
  • Digital Logic Tutorials
  • Internet of Things Tutorials
  • Internet Tutorials
  • Interview questions answers
  • Java Tutorials
  • Javascript Tutorials
  • Linux
  • Machine Learning Tutorials
  • Operating Systems Tutorials
  • Programming Tutorials
  • Projects
  • Tips&Tricks
  • Tools
  • VBScript Tutorials
  • Java Interview Questions and Answers (2023)
    Thinking of becoming a Java developer? I must say it’s a good choice! Java is continuously named the most popular programming language. And the...

    Learn More “Java Interview Questions and Answers (2023)” »

  • Iot(Internet of things) in healthcare
    IoT in Healthcare
    IoMT (Internet of Medical Things) stands for devices that can collect and exchange data – either with users or other devices via the internet,...

    Learn More “IoT in Healthcare” »

  • four stages of iot solution for industry
    IoT for Industry
    In this post, we are going to learn about use cases of IoT for Industry and four stages for providing IoT solutions. Machine Diagnosis...

    Learn More “IoT for Industry” »

  • Iot for agricultural
    IoT in Agriculture
    IoT technology has realized smart wearables, connected devices, automated machines, and driverless cars. However, in agriculture, the IoT has brought the greatest impact. Amongst the challenges...

    Learn More “IoT in Agriculture” »

  • Iot for logistics
    IoT in Logistics and Supply Chain
    IoT applications for smart logistics and supply chain systems:  Logistics Fleet Tracking  To track the locations of the vehicles in real time, the vehicle...

    Learn More “IoT in Logistics and Supply Chain” »

Copyright © 2023 Programmingoneonone.

Powered by PressBook Blog WordPress theme