{"id":9256,"date":"2022-08-25T09:04:34","date_gmt":"2022-08-25T09:04:34","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9256"},"modified":"2022-12-14T11:39:35","modified_gmt":"2022-12-14T11:39:35","slug":"max-heap-in-java","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/max-heap-in-java\/","title":{"rendered":"Max Heap in Java"},"content":{"rendered":"

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

What is Heap?<\/h3>\n

Heap is a special kind of complete binary tree<\/a> in which the all node has a value greater (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 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 .
\n\"\"<\/p>\n

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

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

A Heap in which all nodes have a value greater than all its children , is Max heap .
\ni.e for a node its value is more 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 more value than all nodes below its level. <\/p>\n

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

    \"\"<\/p>\n

      \n
    • \n

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

    • \n

      Value of node at 0 is greater than the value of nodes at 1 and 2.<\/p>\n<\/li>\n

    • \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<\/li>\n

    • \n

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

    • \n

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

      Operations on Max heap<\/h3>\n

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

      deleteMax() :<\/strong> The method will delete the node with maximum 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 MaxHeap class . The method ensures that heap property is maintained .<\/p>\n

        insert() :<\/strong> The method is used to insert new nodes in the max 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 getMax() and size().<\/p>\n

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

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

        We can also implement max heap using PriorityQueue class . By default it creates a min heap , to create a max heap we can use Collections.reverseOrder() .<\/p>\n\t\t\t\t\t\t