Heaps

Question 1

What is a heap?

Answer 1

A special tree-based data structure that satisfies the heap property.

Question 2

What is the heap property?

Answer 2

In a max-heap, each parent is greater than or equal to its children; in a min-heap, each parent is less than or equal to its children.

Question 3

What is a max-heap?

Answer 3

A heap where the largest element is at the root.

Question 4

What is a min-heap?

Answer 4

A heap where the smallest element is at the root.

Question 5

What is a binary heap?

Answer 5

A binary tree that maintains the heap property and is complete (all levels filled except possibly the last).

Question 6

What is a priority queue?

Answer 6

An abstract data type where each element has a priority and elements are served based on priority.

Question 7

How is a priority queue typically implemented?

Answer 7

Using a binary heap.

Question 8

What are the main operations of a heap?

Answer 8

Insert, extract-min/extract-max, peek-min/peek-max, and heapify.

Question 9

What is the time complexity of inserting into a binary heap?

Answer 9

O(log n)

Question 10

What is the time complexity of extracting the root from a binary heap?

Answer 10

O(log n)

Question 11

What is the time complexity of peeking at the root of a heap?

Answer 11

O(1)

Question 12

What is heapify?

Answer 12

The process of rearranging elements to maintain the heap property.

Question 13

What is the time complexity of heapify?

Answer 13

O(log n) for a node, O(n) for an entire array.

Question 14

What is build-heap?

Answer 14

Converting an arbitrary array into a heap.

Question 15

What is the time complexity of build-heap?

Answer 15

O(n)

Question 16

How is a heap represented in an array?

Answer 16

The root is at index 0, left child at 2i+1, right child at 2i+2.

Question 17

What is the parent index of a node at index i in a heap array?

Answer 17

(i - 1) // 2

Question 18

How do you insert into a heap?

Answer 18

Add the element to the end and bubble it up to restore the heap property.

Question 19

How do you remove the root of a heap?

Answer 19

Replace it with the last element and bubble it down (heapify).

Question 20

What is the space complexity of a heap with n elements?

Answer 20

O(n)

Question 21

What is a complete binary tree?

Answer 21

A binary tree where all levels are fully filled except possibly the last, which is filled left to right.

Question 22

What is a d-ary heap?

Answer 22

A generalization of a binary heap where each node has d children.

Question 23

What is a Fibonacci heap?

Answer 23

A complex heap structure with better amortized performance for some operations.

Question 24

What is the time complexity of decrease-key in a Fibonacci heap?

Answer 24

O(1) amortized.

Question 25

What is the benefit of heaps in Dijkstra’s algorithm?

Answer 25

Efficiently retrieves the next node with the lowest tentative distance.

Question 26

What is a common application of heaps?

Answer 26

Priority scheduling, Dijkstra’s algorithm, Huffman encoding.

Question 27

How do you implement a priority queue with changing priorities?

Answer 27

Use a decrease-key or update operation if supported.

Question 28

What is heap sort?

Answer 28

A comparison-based sorting algorithm that uses a heap.

Question 29

What is the time complexity of heap sort?

Answer 29

O(n log n)

Question 30

Is heap sort stable?

Answer 30

No, it is not a stable sort.

Question 31

Is heap sort in-place?

Answer 31

Yes, it uses constant extra space.

Question 32

How do you find the k largest elements in an array?

Answer 32

Use a min-heap of size k.

Question 33

How do you find the k smallest elements in an array?

Answer 33

Use a max-heap of size k.

Question 34

What is a min-priority queue?

Answer 34

A priority queue that serves elements with the smallest priority value first.

Question 35

What is a max-priority queue?

Answer 35

A priority queue that serves elements with the largest priority value first.

Question 36

What is the difference between a queue and a priority queue?

Answer 36

Queue is FIFO; priority queue is based on priority.

Question 37

What happens if you insert elements with equal priority in a heap?

Answer 37

Order is not guaranteed; depends on implementation.

Question 38

Can a heap be used for real-time scheduling?

Answer 38

Yes, to schedule tasks by priority or deadline.

Question 39

What is a k-ary heap?

Answer 39

A heap where each node has up to k children.

Question 40

What is lazy deletion in a heap?

Answer 40

Marking elements as deleted instead of removing them immediately.

Question 41

What is the root of a heap?

Answer 41

The element with the highest priority — either max or min.

Question 42

What is an advantage of using a heap over a sorted list?

Answer 42

Faster insertions and deletions (O(log n) vs O(n)).

Question 43

What is the disadvantage of heaps?

Answer 43

They do not support fast search or ordered traversal.

Question 44

How is a heap used in median-finding algorithms?

Answer 44

Use two heaps: a max-heap for the lower half and a min-heap for the upper half.

Question 45

What is a skew heap?

Answer 45

A self-adjusting heap without structural constraints.

Question 46

What is a leftist heap?

Answer 46

A binary heap variant that favors the shortest path to a leaf on the right.

Question 47

What is the amortized cost of operations in a Fibonacci heap?

Answer 47

Insert and decrease-key are O(1); extract-min is O(log n).

Question 48

What is the best-case time complexity of insert in a binary heap?

Answer 48

O(1), when the element is placed without bubbling up.

Question 49

Can you use a heap for top-k problems?

Answer 49

Yes, by maintaining a heap of size k.

Question 50

What is the difference between a binary search tree and a heap?

Answer 50

A BST supports ordered traversal; a heap supports efficient max/min retrieval.