Chapter 6: Heapsort Flashcards
1
Q
Heap
A
Basically like a binary tree, representing an array. The indices count from left to right down the different levels of the tree
2
Q
Max-Heap
A
Has the largest element as the root and no parent node can have child nodes larger than itself.
3
Q
The left child of a node at index i in a heap will always be at index…
A
2i
4
Q
The right child of a node at index i in a heap will always be at index…
A
2i + 1
5
Q
Viewing a heap as a tree, we define the height of a node in a heap to be
A
the number of edges on the longest simple downward path from the node to a leaf
6
Q
Height of a binary tree with n elements
A
O(lgn)
