Heap

📌 What is heap?

1
2

1️⃣ A Heap is a special Tree-based data structure in which the tree is a complete binary tree. 
2️⃣ All the nodes of the heap are arranged in a specific order.

In Java, PriorityQueue can be used as a Heap.

📌 Then, what is PriorityQueue?

1

A PriorityQueue is used when the objects are supposed to be processed based on the priority

By default, the priority queue in Java is min Priority queue with natural ordering. To make it max, we have to use a custom comparator so that head of the queue returns the greatest element in the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 1. declare
//  min-heap
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//  max-heap
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

// 2. add
priorityQueue.add(1); 
priorityQueue.add(2);   
priorityQueue.offer(3);

// 3. remove 
priorityQueue.poll();   // get data and remove it
priorityQueue.remove(); // only remove
priorityQueue.clear();

// 4. get
priorityQueue.peek(); // only get

📌 Feature

Generally, Heaps can be of two types:

• Min-Heap

  In a Min-Heap, the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

  1 2 3 4 5

  PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); // ex. [1, 3, 5] // get the minimum value at the moment System.out.println(heap.poll()); // 1 System.out.println(heap.poll()); // 3

• Max-Heap

  In a Max-Heap, the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

  1 2 3 4 5 6 7 8 9 10 11 12 13

  PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // same as PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return - Integer.compare(o1, o2); } }); // ex. [1, 3, 5] // get the maximum value at the moment System.out.println(heap.poll()); // 5 System.out.println(heap.poll()); // 3

📌 Implementation

Task 1

The source : https://stackoverflow.com/questions/14165325/is-there-a-heap-in-java
https://www.geeksforgeeks.org/heap-data-structure/
https://coding-factory.tistory.com/603