Heaps

Question 1

How to construct a heap from an array (high level)

Answer 1

1) repeated insertions (log linear) or 2) the Floyd algorithm (linear time)

Question 2

What data structure are heaps implemented with?

Answer 2

Arrays. This is a key difference from trees which are usually implemented with pointers (non contiguous memory)

Question 3

Min heap property

Answer 3

The key of a child is always greater than or equal to the key of the parent

Question 4

Heaps use what data structure to avoid holes in the array?

Answer 4

Complete binary trees. complete binary tree is a tree where each node has at most two children and the nodes at all levels are full, except for the leaf nodes which can be empty.

Question 5

Build max heap from array

Answer 5

This is Kadens algo. Linear time

1) visually represent array as complete binary tree
2) start from last element of array and a) for each element, “heapify” it, meaning you ensure it is larger than both it’s children. If it’s not larger than both it’s children , you swap it with the larger of its children. b) you then call heapify on the child you did the swap with (so essentially heapify does recursion), because that child may now be smaller than IT’S children

Question 6

Build max heap from array naive time complexity

Answer 6

O(nlgn), but the real runtime is actually O(n)

Question 7

Heapsort

Answer 7

1) build min heap from array
2) delete/remove min element from heap (logn time bc must maintain heap property) and place into first el of New array
3) repeat #2, removing the ith min element and placing into the ith element of the new array (starting i at zero for both)until the heap is empty

Resulting array is sorted in increasing order

Question 8

What index is the root often placed at?

Answer 8

1, to simplify arithmetic

Question 9

Mergeable heap

Answer 9

heap (also called a meldable heap) is an abstract data type, which is a heap supporting a merge operation (e.g to merge with another heap)

Question 10

List 5 examples of mergeable heap data structures

Answer 10

Binomial heap
Fibonacci heap
Leftist tree
Pairing heap
Skew heap

These all have more efficient merge operations than the naive merge algorithm for a binary heap

Question 11

In most mergeable heap data structures what is the operation on which others are based

Answer 11

Merging

Question 12

In most mergeable heap data structures how is insert implemented?

Answer 12

by merging a new single-element heap with the existing heap

Question 13

In most mergeable heap data structures how is delete impelemented?

Answer 13

by merging the children of the deleted node.

Question 14

Give a naive implementation of meld for a binary heap

Answer 14

X = extractMin H2
While X != null
Insert X, H1
X = extractMin H2

While both the heaps have to maintain the heap property (which would intuitively lead to nlgn time for the whole process), that one proof on build heap time shows that it takes O(n) [… but I think that’s for kadens algorithm for building heaps . . . Not for this algorithm for naive binary merge]

Question 15

Chen 2007 study

Answer 15

examined priority queues specifically for use with Dijkstra’s algorithm and concluded that in normal cases using a d-ary heap without decrease-key (instead duplicating nodes on the heap and ignoring redundant instances) resulted in better performance, despite the inferior theoretical performance guarantees.

Question 16

Heap decrease-key operation

Answer 16

decrease-key (optional): remove the subtree rooted at the key to be decreased, replace the key with a smaller key, then meld the result back into the heap.

Question 17

Daniel Larkin 2014

Answer 17

They concluded that d-ary heaps such as binary heaps are faster than all other heap implementations when the decrease-key operation is not needed (and hence there is no need to externally track the location of nodes in the heap), but that when decrease-key is needed pairing heaps are often faster than d-ary heaps and almost always faster than other pointer-based heaps, including data structures like Fibonacci heaps that are theoretically more efficient

Question 18

PriorityQueue.poll()

Answer 18

retrieve and remove the head of this queue, or returns null if this queue is empty

Question 19

SmoothSort

Answer 19

a variant of heapsort; The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state.

Question 20

JavaScript Implementation of insert for a heap

Answer 20

Insert(x) {

this. heap.push(x) // where heap is a JS array
this. siftup(this.heap.length - 1)

}

siftup(i) { // recursive implementation
// remember we’re using 1-based heaps 
if (i == 1) { // if i=1, we’re at the top of the heap and can’t sift up anymore
 return 
} 

let p = Math.floor(i/2)
if (this.comparator(this.heap[i], this.heap[p])) {
; [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]]; //swap 
 this.siftup(p) // continue sifting the element, now at index p 
}
}

siftup(i) { // iterative implementation
if (i===1) { return } // this is the root element and can’t be sifted up anymore
let p = Math.floor(i/2)
while (this.comparator(this.heap[i], this.heap[p] && i >= 1) { // bc if i is 1
 [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]] 
  i = p
  p = Math.floor(p/2)
}
}

Question 21

Heapify implementation

Answer 21

//given a heap where the parent does not satisfy the heap property with one or more of its children
//aka sift down. Used as part of delete 
heapify(i){ // for min heap

let smallest = i 
if(2* i <= this.heap.length - 1 && this.heap[2*i] < this.heap[i]) {
 smallest = 2*i
} 

if (2*i+1 <= this.heap.length - 1 && this.heap[2*i + 1] < this.heap[i]) {
 smallest = 2*i + 1
}
if (smallest !== i) {
swap(this.heap, i, smallest) 
}

Question 22

JavaScript implementation of delete for a heap

Answer 22

Delete(i) {
swap(A, i, this.heap.length - 1)
this.heap.pop()
this.heapify (i)
}

Question 23

Binary heap operations time complexity

Answer 23

Avg and worst case
Insert O(1) and O(n)
Find-min O(1) and O(1)
Delete-min O(logn) and O(logn)

Question 24

Softheap

Answer 24

a kind of priority queue that gives us an optimal

trade-off between accuracy and speed.