# Implementing Max Heap In Java

Heaps

A heap is a tree-based data structure in which all the nodes of the tree are in a specific order.

For example, if X is the parent node of Y, then the value of X follows a specific order with respect to the value of Y and the same order will be followed across the tree.

A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:

• the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
• the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.

A heap is not a sorted structure and can be regarded as partially ordered. As you see from the picture, there is no particular relationship among nodes on any given level, even among the siblings.

A heap is useful data structure when you need to remove the object with the highest (or lowest) priority.

A common use of a heap is to implement a priority queue.

A Binary Heap is a Complete Binary Tree. A binary heap is typically represented as an array.

• The root element will be at Arr.
• Below shows indexes of other nodes for the ith node, i.e., Arr[i]:

? Arr[(i-1)/2] : Returns the parent node

? Arr[(2*i)+1] : Returns the left child node

? Arr[(2*i)+2] : Returns the right child node

The traversal method use to achieve Array representation is Level Order

• Operations on Max Heap: 1) peek(): It returns the root element of Max Heap. This is the maximum element of heap. Time Complexity of this operation is O(1). 2) poll(): Removes the maximum element from MaxHeap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()) after removing root. 3) add(): Inserting a new key takes O(Logn) time. We add a new key at the end of the tree. IF new key is smaller than its parent, then we don?t need to do anything. Otherwise, we need to traverse up to fix the violated heap property.

Below is the simple Java implementation of a Max Heap :