Heaps Flashcards
Heapsort is an ___ sort and not a ___ sort.
In Place: Only a constant number of array elements are stored outside the input array at any time
Stable
Fully binary tree
A binary tree in which each node is either a leaf or has degree exactly 2.
Complete binary tree
A binary tree in which all leaves are on the same level and all internal nodes have degree 2.
Height of a node:
The number of edges on the longest simple path from the node down to a leaf.
Level of Node:
The length of a path from the root to the node.
Height of tree
Height of root node.
A binary tree of height (depth) d has at most ___ nodes
2^(d+1)
A binary tree with n nodes has height at least __.
lg n
Heap
A nearly complete binary tree with the following two properties:
- Structural property: All levels are full, except possibly the last one, which is filled from left to right.
- Heap Property: for any node x, Parent(x) >= x.
Max-Heapify function
Maintain/Restore the max-heap property.
Build-Max-Heap
Create a max-heap from an unordered array.
Heapsort
Sort an array in place.
Running time of Max-Heapify is
O(log n)
Can be written in terms of the height as being O(h)
Since height is log n.
Running time of BUILD-Max_Heap
O(n)
Running time of Heapsort
O(n log n)
