Heaps

Question 1

A special queue where the key with the highest priority is found at one end

Used to schedule jobs on a computer shared among multiple users

Answer 1

Priority queues

Question 2

1) the higher the key,

Answer 2

the greater the priority

Question 3

2) the key indicates

Answer 3

the execution time (lower is faster)

Question 4

Implementation of priority queues using a linked list

Answer 4

insert – O(1)
delete min – O(n)

Question 5

Implementation of priority queues using a sorted linked list

Answer 5

insert – O(n)
delete min – O(1)

Question 6

An array that we can view as a nearly complete binary tree

Answer 6

(Binary) Heap

Question 7

The tree is full on all levels except possibly

Answer 7

the bottom level (which is filled from left to right)

Question 8

Each node of the tree is

Answer 8

an element of the array

Question 9

The number of elements in the heap stored in an attribute

Answer 9

Heap-size

Question 10

If heap-size = 0,

Answer 10

heap is empty

Question 11

Given a heap represented by an array 𝐴, the root of the tree is at

Answer 11

𝐴[1]

Question 12

For any node at index 𝑖,
a. its parent is at

Answer 12

index i / 2

Question 13

b. its left child is at

Answer 13

index 2𝑖

Question 14

c. its right child is at

Answer 14

index 2𝑖 + 1

Question 15

𝐴[𝑝𝑎𝑟𝑒𝑛𝑡(𝑖)] ≥ 𝐴[𝑖]

Answer 15

Max-heap

Question 16

For every node other than the root, the value of a node is

Answer 16

at most, the value of its parent

Question 17

The largest value in a max-heap is at

Answer 17

the root

Question 18

𝐴[𝑝𝑎𝑟𝑒𝑛𝑡(𝑖)] ≤ 𝐴[𝑖]

Answer 18

Min-heap

Question 19

For every node other than the root, the value of a node is

Answer 19

at least, the value of its parent

Question 20

The smallest value in a min-heap is at

Answer 20

the root

Question 21

We insert at the next available location

Answer 21

Heap insertion

Question 22

Fixup: percolate up aka

Answer 22

Sift-up, float up, *min-heapify

Question 23

To delete the min/max,

Answer 23

1) swap it with the last key
2) subtract heap-size by 1
3) do a fixup from the root (percolate down)

Question 24

Converts an array into a min- / max-heap

Starting from index i / 2 down to 1, percolate down

Answer 24

Build min- / max-heap

Question 25

Using a heap for a priority queue,

Answer 25

insert – O(log n)
delete min/max – O(log n)
build-heap – O(n)

Question 26

A sorting algorithm that calls build-max-heap, then performs N-1 delete-max operations

Answer 26

Heapsort