Questions Chapter 12 Flashcards
What does the term “complete” mean when applied to binary trees?
all the rows are filled with nodes, except possibly the bottom one.
What does the term weakly ordered mean when applied to heaps?
both the right and left children have keys less than (or equal to) the parent
In a heap, a node is always removed from the _____.
root
To “trickle up” a node in a descending heap means:
a. to repeatedly exchange it with its parent until it’s larger than its parent
b. to repeatedly exchange it with its child until it’s larger than its child
c. to repeatedly exchange it with its child until it’s smaller than its child
d. to repeatedly exchange it with its parent until it’s smaller than its parent
a. to repeatedly exchange it with its parent until it’s larger than its parent
A heap can be represented by an array because a heap
is a binary tree
The last node in a heap is always:
a. a left child
b. a right child
c. on the bottom row
d. never less than its sibling
c. on the bottom row
A heap is to a priority queue as a(n) __________ is to a stack
linked list
Insertion into a descending heap involves trickle ______.
up
A heap is an implementation of an ADT ____________
priority queue
removal of the largest item, insertion in a heap is _______ time
O(N*logN)
In a heap, the largest item is always at the ______
root
True or False: Heaps support ordered traversal of the data, locating an item with a specific key, and deletion.
False
A heap is usually implemented as a(n) ______ representing a complete ______ tree.
array, representing a complete binary tree
Each node has a key __________ than its parents and __________ than its children
each node has a key less than its parents and greater than its children
An item to be inserted in a heap is always placed in the first vacant cell of the array and then trickled ____ to its appropriate position
trickled up