tags:
  - school
  - bsu
  - cs321
  - data-structures
  - algorithms
  - notes
  - fall-2024
source: https://github.com/BoiseState/CS321-resources/blob/master/notes/amit/chapter06.pdf
created: 2024-09-18

Introduction

What is the approximate runtime of heapsort?
The approximate runtime of heapsort is .

Like insertion sort, heapsort runs ...
Like insertion sort, heapsort runs in-place.

What is the space complexity of heapsort?
The space complexity of heapsort is .

What data structure does heapsort use to manage information?
The data structure heapsort uses to manage information is a heap.

Heaps

What data type is a binary heap?
A binary heap is an array data type.

What are the two properties that make an array object a binary heap?
The two properties that make an array object a binary heap are:

It can be viewed as a nearly complete binary tree.
The values of the heap satisfy a heap property.

What is a max-heap?
A max-heap is a heap property where the value at a node is the value at its child node(s).

What is a min-heap?
A min-heap is a heap property where the value at a node is the value at its child node(s).

What attribute does an array which represents a heap have?
An array which represents a heap has a heap-size attribute.

What does the heap-size attribute of an array represent?
The heap-size attribute of an array represents how many elements in the heap are stored in the array.

What is the range of values that are in a heap in a given array?
The range of values that are in a heap in a given array is where 1 is the first value and A is the array of values.

What are the bounds for the value of the heap-size attribute?
The bounds for the value of the heap-size attribute is .

Which value in an array is the root of the heap?
The value in an array that is the root of a heap is A[1] or the first value.

What is the function that finds the parent of a node in a heap given an index ?
The function that finds the parent of a node in a heap given an index is .

If a node is at index , how do you find its parent?
If a node is at index , you find its parent by calculating .

How can you calculate using bitwise operations?
You can calculate using bitwise operations by calculating .

What is the function that finds the left child of a node in a heap given an index ?
The function that finds the left child of a node in a heap given an index is .

If a node is at index , how do you find its left child?
If a node is at index , you find its left child by calculating .

How can you calculate using bitwise operations?
You can calculate using bitwise operations by calculating .

What is the function that finds the right child of a node in a heap given an index ?
The function that finds the right child of a node in a heap given an index is .

If a node is at index , how do you find its right child?
If a node is at index , you find its right child by calculating .

How can you calculate using bitwise operations?
You can calculate using bitwise operations by calculating .

The max-heap property states that for every node other than the root in an array , .
The max-heap property states that for every node other than the root in an array , .

The min-heap property states that for every node other than the root in an array , .
The min-heap property states that for every node other than the root in an array , .

The largest / smallest element in a max-heap / min-heap is at the ...
The largest / smallest element in a max-heap / min-heap is at the root.

What would the array look like as a binary tree?
The array as a binary tree would look like:

What is the height of a heap with nodes?
The height of a heap with nodes is .

What is the maximum number of nodes a heap of height will have?
The maximum number of nodes a heap of height will have is .

What is the minimum number of nodes a heap of height will have?
The minimum number of nodes a heap of height will have is .

Maintaining the Heap Property

What is the pseudocode for the MAX-HEAPIFY function?
The pseudocode for the MAX-HEAPIFY function is:

MAX-HEAPIFY(A, i) // Heapification downward
	l = LEFT(i)
	r = RIGHT(i)
	if l <= A.heap_size and A[l] > A[i]
		largest = l
	if r <= A.heap_size and A[r] > A[largest]
		largest = r
	if largest != i
		exchange A[i] with A[largest]
		MAX-HEAPIFY(A, largest)

What is the running time of the MAX-HEAPIFY function?
The running time of the MAX-HEAPIFY function is , where .

Building a Heap

What does the BUILD-MAX-HEAP function do?
The BUILD-MAX-HEAP function uses a bottom-up approach to convert an array to a max-heap by calling a sequence of MAX-HEAPIFY procedures.

Where does the BUILD-MAX-HEAP function start?
The BUILD-MAX-HEAP function starts at the last non-leaf node.

Where does the BUILD-MAX-HEAP function end?
The BUILD-MAX-HEAP function ends at the root node.

What is the pseudocode for the BUILD-MAX-HEAP function?
The pseudocode for the BUILD-MAX-HEAP function is:

BUILD-MAX-HEAP(A)
	// A[1:n] is an unsorted array
	A.heap_size = n
	for i = n / 2 downto 1 // Skip the leaves
	do MAX-HEAPIFY(A, i)

About how many times does the BUILD-MAX-HEAP function call the MAX-HEAPIFY function?
The BUILD-MAX-HEAPIFY function calls the MAX-HEAPIFY function about times.

What is the running time of the BUILD-MAX-HEAP function?
The running time of the BUILD-MAX-HEAP function is .

What is the tight upper bound of the BUILD-MAX-HEAP function?
The tight upper bound of the BUILD-MAX-HEAP function is .

The Heapsort Algorithm

What are the three steps of the heapsort algorithm?
The three steps of the heapsort algorithm are:

Make the input array a max-heap by calling BUILD-MAX-HEAP(A).
Exchange with and then decrement by one.
Call MAX-HEAPIFY(A,1) to re-heapify .

What is the pseudocode of the heapsort algorithm?
The pseudocode of the heapsort algorithm is:

HEAPSORT(A)
	// Array A[1:n] is unsorted
	for i = n downto 2
		A.heap_size = A.heap_size - 1
		MAX-HEAPIFY(A, 1)

How many times does the HEAPSORT function call the BUILD-MAX-HEAP function?
The HEAPSORT function calls the BUILD-MAX-HEAP function times.

What is the running time of the heapsort algorithm?
The running time of the heapsort algorithm is .

What is the loop invariant of the heapsort algorithm?
The loop invariant of the heapsort algorithm is:

At the start of each iteration of the for loop of lines 2-5, the subarray is a max-heap containing the smallest elements of , and the subarray contains the largest elements of , sorted.

Priority Queues

What is a priority queue?
A priority queue is a data structure for maintaining a set of elements, each with an associated value.

What is the name of the value associated with each element in a priority queue?
The name of the value associated with each element in a priority queue is the key.

What are the four operations a max-priority queue supports efficiently?
The four operations a max-priority queue supports efficiently are:

Insert.
Maximum.
Extract-max.
Increase-key.

What are the four operations a min-priority queue supports efficiently?
The four operations a min-priority queue supports efficiently are:

Insert.
Minimum.
Extract-min.
Decrease-key.

...

What are two examples of what you can use a priority queue for?
Two examples of what you can use a priority queue for:

A job scheduler.
Discrete event simulation.

What is the pseudocode for the MAX-HEAP-MAXIMUM function?
The pseudocode for the MAX-HEAP-MAXIMUM function is:

MAX-HEAP-MAXIMUM(A)
	// O(1) time
	if A.heap_size < 1
		error "Heap underflow"
	return A[1]

What is the pseudocode for the MAX-HEAP-EXTRACT-MAX function?
The pseudocode for the MAX-HEAP-EXTRACT-MAX is:

MAX-HEAP-EXTRACT-MAX(A)
	// O(lg n) time
	max = MAX-HEAP-MAXIMUM(A)
	A[1] = A[A.heap_size]
	A.heap_size = A.heap_size - 1
	MAX-HEAPIFY(A, 1)
	return max