Heap Sort Flashcards
What is a heap data structure?
An ordered binary tree
What is a max heap?
A heap where the value of parent nodes is greater than the value of child nodes.
What is an in-place algorithm?
An algorithm that operates directly on the input data structure and does not require any extra space
What are two in place sorting algorithms?
Heapsort, quicksort
What are applications of the heap data structure?
Heap sort, priority queue.
What is a nearly complete binary tree?
A tree that is completely filled on all levels except possibly the lowest which is filled from left up to a point.
What is a complete k-ary tree
A k-ary tree in which all leaves have the same depth and all internal nodes have degree k (CLRS)
How many internal nodes does a complete binary tree have?
2^h - 1 (where h is height)
With starting index at 1, what index is the root of the tree?
1
With starting index at 1, what index is the parent of the A[i]?
A[floor(i/2)]
With starting index at 1, what index is the left child of A[i]?
A[2i]
With starting index at 1, what index is the right child of A[i]?
A[2i + 1]
What is the height of node in a heap?
edges on the longest simple downward path from the node to a leaf
What is a min-heap?
Opposite of max heap; root has the smallest element
What is a priority queue?
A data structure for maintaining a set S of elements, each with an associated value called a key. It is a sorted Queue data structure.
