Heap Fundamentals - Priority Queue / Heap / Introduction

Problems
1

https://algo.monster/problems/heap_intro

2

you could simplify the pop() function in the JS implementation by doing this:
this.heap[0] = this.heap.pop()

instead of doing two separate operations

this.heap[0] = this.heap[this.size() - 1];
this.heap.pop();
3

for java, you could just use PriorityQueue<Integer> heap = new PriorityQueue<>(arr);

6

Is it allowed to use builtin libraries in interview instead of implementing on my own?

7

Duplicate key allowed in C++ priority_queue ?

8

If the JS implementation was simplified to: this.heap[0] = this.heap.pop(),
then the heap cannot be empty.
In other words, if the minHeap currently only has 1 value, and you want to pop the only element in the heap, that value will be reassigned back to where it originally was, at the 0th index, this.heap[0].

10

Array.size() is not a valid method in JavaScript in line 38 of the min-heap in Javascript code.

11

I take my words back, size() is in the later part of the code.

12

Excellent introduction to Heaps. It seems like the articles and sections are written by different contributors. Give this person a raise and more articles to write.

13

Some of the other articles were a bit underwhelming

14

what is swap

15

The optimal java solution should be the following:
runtime: O(nlog3)
memory: O(3)

public static List<Integer> heapTop3(List<Integer> arr) {
        var pq = new PriorityQueue<Integer>((a, b)->Integer.compare(b, a)); // max heap
                                            
        for (int n : arr) {
            pq.offer(n);
            if (pq.size() > 3) {
                pq.poll();
            }
        }
        var res = new LinkedList<Integer>();
        for (int i = 0; i < 3; i++) {
            res.addFirst(pq.poll());
        }
        return res;
    }
16

In the “Is it a heap?” game, there is a type for the 4th example from top left. It is not a heap because 5 < 7 (the root to leaf path is not sorted). But the page says - 5 < 9 - this can confuse a lot of newbies . The heap property needs to be maintained from top to bottom - not with siblings or across levels, right?

17

Heap is a complete BINARY tree, which is not mentioned anywhere.

18

or not?

anyways, it should be clarified somewhere, as the “is this heap” game seems implying that heaps are binary trees while later in the section, the writer only says heap is complete tree but never mentions if it’s binary tree or not.

19

Binary heap is the most common heap structure in programming, but there are other k-ary heaps where each node could have k children.

20

thanks, updated the figure

21

thanks! I gave myself a raise!

22

manipulate the left or right pointers of the two nodes such that their position in the tree are switched

23

for heap, you can use builtin libs.