{"id":9259,"date":"2022-08-25T12:06:34","date_gmt":"2022-08-25T12:06:34","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9259"},"modified":"2022-12-14T11:42:18","modified_gmt":"2022-12-14T11:42:18","slug":"min-heap-in-java","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/min-heap-in-java\/","title":{"rendered":"Min Heap in Java"},"content":{"rendered":"

\"\"<\/p>\n<\/p>\n

What is Heap?<\/h3>\n

Heap is a special kind of complete binary tree in which the all node has a value greater
\n(or smaller ) than all of its children . <\/p>\n

A complete binary tree is a binary tree where all levels are completely filled except the last level which can be complete or incomplete . All nodes should be filled from left to right . <\/p>\n

There are two types of heap , [Min heap](https:\/\/prepbytes.com\/blog\/heap\/min-heappaid\/ “Min heap”) and Max heap . In Max heap all nodes have value greater than the children\u2019s value whereas in Min heap all nodes have value smaller than the children\u2019s value .<\/p>\n

\"\"<\/p>\n

In this Article we will focus on Min heap only .<\/p>\n

What is Min-heap?<\/h3>\n

A Heap in which all nodes have a value smaller than all its children , is [Min heap](https:\/\/prepbytes.com\/blog\/heap\/min-heappaid\/ “Min heap”) .
\ni.e for a node its value is less than the value of its left child and the value of its right child and this property is recursively true for every node .In other words , we can also say that any node
\nat a certain level has less value than all nodes below its level. <\/p>\n

Representation of Min-heap<\/h3>\n
    \n
  1. A Min heap is represented using an Array . <\/li>\n
  2. A node at i-th position has its left child at 2 i+1 and right child at 2 <\/em> i+2 .<\/li>\n
  3. A node at i-th position has its parent at (i-1)\/2 .<\/li>\n
  4. In min heap , heap[i] < heap[2 i+1] and heap[i] < heap[2 <\/em> i+2]<\/li>\n<\/ol>\n

    \"\"<\/p>\n

    Node at position 0 has left child at 20+1 = 1 and right child at 2 <\/em> 0+2 = 2 positions .
    \nValue of node at 0 is smaller than the value of nodes at 1 and 2.<\/p>\n

    Node at position 1 has left child at 2 1+1 = 3 and right child at 2 <\/em> 1+2 = 4 positions .<\/p>\n

    Node at position 2 has only left child at position 2 * 2+1=5 . <\/p>\n

    Nodes at position 3,4 and 5 are leaf nodes with no child .<\/p>\n

    Operations on Min heap<\/h3>\n

    getMin() :<\/strong> This method will return the minimum number in the heap . <\/p>\n

    deleteMin() :<\/strong> The method will delete the node with minimum value .Following steps are taken in this method :<\/p>\n

      \n
    1. Swap root node with the rightmost node .<\/li>\n
    2. Delete rightmost node<\/li>\n
    3. Call heapify method for root
      \nBecause of heapify() , the time complexity of this method is O(logn) .<\/li>\n<\/ol>\n

      heapify() :<\/strong> This will be the private method for the MinHeap class . The method ensures that heap property is maintained . <\/p>\n

      insert() :<\/strong> The method is used to insert new nodes in the min heap . A new node is inserted at the end of the heap array , and we keep on swapping this node with the parent node if it is violating heap property .<\/p>\n

      size() :<\/strong> returns size of heap.<\/p>\n

      Time complexity of all operations is O(logn) except getMin() and size().<\/p>\n

      Implementation of Min heap in Java<\/h3>\n

      Implementation of Min heap using java libraries<\/strong> <\/p>\n

      We can also implement max heap using PriorityQueue class .By default it creates a min heap.<\/p>\n\t\t\t\t\t\t