Heap Data Structure (java)

essentially Heap is a tree based data structure stored as an array.
In array we arrange the elements of a tree level order wise and the parent node is always (i-1)/2 from any index i = {0,n-1} for an n-sized array.
The child nodes are for a parent left child node = (2i+1) and right child node is = (2i+2).

as you can see here there is 2i and 2i+1 for child nodes which means we can take it like this if we start with 1 based indexing i hope this is clear.

In java we use priorityQueues to store the heap.
Heap is primarily 2 types :- minHeap() and maxHeap()

peek() → 10 O(1)
remove() → 10 O(log n)
insert() -> O(log n)
PriorityQueue is a part of the java.util package and is a queue that orders elements based on their priority.

• The default implementation of PriorityQueue uses a Min-Heap (smallest element at the top).
• Max-Heap can be implemented by providing a custom comparator.

https://leetcode.com/discuss/post/6149018/heap-and-priority-queue-in-java-cheat-sh-276e/
good reference attached.

Get Arvindersingh’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Max Heap : parent>children and MinHeap : parent<children nodes

Lets do heap construction from a random array :
given : [10, 5, 20, 2, 8, 15, 30] want to heapify

take the last non-leaf elements as leafs are already satisfying because they have no children we need to move the parents right.
Last NON-leaf node = (n/2–1)
in above eg the array is of size n=7 so last non-leaf node is 3(index :2) that is 20. Now the childs of 20 will be 2i+1 and 2i+2 which are 15 and 30.

here we compare parents with both child nodes and try to satisfy property of parent>child for max heap and parent<child for min heap. then we swap them.
and we repeat this process till we reach the root node that is index 0.

Insert → O(log n)
Extract max/min → O(log n)
Peek → O(1)
Build Heap → O(n)

Kth Largest Element in an Array
Kth Smallest Element in a Sorted Matrix
Last Stone Weight
Kth Largest Element in a Stream
Take Gifts From the Richest Pile