Quiz 1 Flashcards
What is a heap?
A heap is a tree-like data structure. It is
often used to implement the ADT priority
queue.
What is a binary heap?
A binary heap is a nearly complete binary
tree filled on all levels except possibly the
lowest level where leaves (values) are
pushed left-most.
How are heaps usually implemented?
Heaps are usually implemented as an array.
What does each node of a heap satisfy?
The heap property
What is a max heap?
Every node’s value is larger than (or equal to) the values of its children.
What is a min heap?
Every node’s value is less than (or equal to) the value of its children.
What is a priority queue?
A priority queue is an ADT which has methods for inserting an item and removing the smallest (or largest) item.
True or False: A priority queue can be implemented in several ways – a heap being one – but a heap is a more fundamental data structure.
True
Regarding min heap methods, what is the space-time complexity of Min(h)?
O(1)
Regarding min heap methods, what is the space-time complexity of Insert(H, k)?
O(log(n))
Regarding min heap methods, what is the space-time complexity of DeleteMin(H)?
O(log(n))
What min heap method removes the root, places the right-most leaf into the root position and moves down the node until the heap property is satisfied?
DeleteMin(h)
An array A that represents a heap is an object with what two attributes?
A.length, A.heap-size
Regarding a heap, what is the space-time complexity of determining a position?
O(1)
The heap property is what allows operations to be performed quickly. What is the heap property?
The minimum (or maximum) should be the root, and any node should be smaller (or larger) than its descendants.
