Heap Sort

What is a binary tree?

• A structure with nodes connected by edges

• A tree that maintains a specific order between parent and child nodes.

• A sublist created from values in an array

How many children can each node have?

What is the root node in a binary tree?

• The node with no parent

• The node with no children

What is a heap?

What does heapify do?

• Bring the greatest number to the top of the heap

• Move the greatest number to the bottom of the heap

• Remove the greatest number from the bottom of the heap

What happens to a number after it's removed from a heap?

• It gets sorted into its place in the array

• It gets moved to the end of the array

• It moves to the beginning of the array

What is the notation for heap sort's best-case scenario?

• O(n log n)

• O(n log 2)

• O(log n)

What is the notation for heap sort's worst-case scenario?

• O(n log n)

• O(n log 2)

• O(log n)

Is additional memory required for heap sort to function?

• Yes

• No

What would be the next step?

• Use heapify to construct a max binary tree

• Move 4 to the bottom of the heap

• remove 1 from the heap

• move 1 to the beginning of the array