Ch 5: Heaps Flashcards
what is a max-heap?
a complete binary tree that maintains the simple property that a node’s key is greater than or equal to the node’s children’s keys
what is the root node?
a node with the maximum key in the entire tree, and therefore has no parents
what is insert?
an operation that inserts the node into the tree’s last level then swaps node with the parent until no max-heap property violation occurs
how is a level added and when is a new level added during insert?
a level is filled left to right before adding another level so that the tree’s height is always the minimum possible
what is percolating?
an upward movement of a node in a max-heap
what is remove?
an operation that removes the root node by replacing the root with the last level’s last node and swapping that node with its greatest child until no max-heap property violation occurs
what is the height of a max-heap?
logN
what is a min-heap?
similar to a max-heap but a node’s key is less than or equal to its children’s keys
how are heaps typically implemented?
arrays
what is used to refer to the nodes?
indices, not pointers since it is an array and not linked list
what is the formula to find the parent index from the child index?
lower of (i-1)/2
what is the formula to find the child index/indices from the parent index
(2i)+1 / (21i)+2
what is heap sort?
- a sorting algorithm that takes advantage of a max-heap’s properties by repeatedly removing the max and building a sorted array in reverse order
- sorts from least to greatest
what is heapify?
an operation that is used to turn an array into a heap
what is the formula to find the largest internal node index?
lower of N/2 -1
explain how heapsort works
- heapify array into a max-heap and initializing an index value to the size of the array minus 1
- swap last item w root and lower size by 1 (removes last item)
- percolate top node down to satisfy heap ordering property
- repeat until end index is 0
explain the heapsort algorithm
- uses 2 loops to sort an array
- first loop heapifies the array using MaxHeapPercolateDown
- second loop removes the maximum value, stores that value at the end index, and decrements the end index, until the end index is 0
what is a priority queue?
a queue where each item has a priority and items with higher priority are closer to the front of the queue than items with lower priority
what is enqueue for a priority queue?
an operation that inserts an item such that the item is closer to the front than all items of lower priority, and closer to the end than all items of equal or higher priority
what is dequeue for a priority queue?
an operation that removes and returns the item at the front of the queue, which has the highest priority
is the priority the same for every priority queue?
no, it can be changed for each queue, sometimes it compares the data, sometimes it compares the priority value, sometimes order is least-greatest or greatest-least
what is peek for a priority queue?
an operation that returns the highest priority item, without removing the item from the front of the queue
what is EnqueueWithPriority for a priority queue?
an enqueue operation that includes an argument for the enqueued item’s priority
what is the common way to implement priority queues?
heaps
what is sorting?
the process of converting a list of elements into ascending or descending order
what is shell sort?
a sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm
what is a gap value?
a positive integer representing the distance between elements in an interleaved list
how are gap values used in shell sort?
shell sort uses gap values to determine the number of interleaved lists
how are interleaved lists created?
- starting at the first index, that node is part of list 1
- the next node for that list is the current node’s index + gap value
- continue until end of list is reached
- then go back to first index and move over by 1, repeat list creation until all nodes are separated
does shell sort work if the interleaved lists do not have the same amount of elements?
yes, some lists may have less elements than the others but shell sort still works
what is quicksort?
a sorting algorithm that repeatedly partitions the input into low and high parts(each part is unsorted) and then recursively sorts each of those parts
what is a pivot?
any value within the array being sorted, commonly the value of the middle array element
how is a pivot used in quicksort?
to partition the input, quicksort chooses a pivot to divide the data into low and high parts
what is merge sort?
a sorting algorithm that divides a list into two halves recursively sorts each half, then merges the sorted halves to produce a sorted list, the recursive partitioning continues until a list of 1 element is reached, as a list of 1 element is already sorted
what is radix sort?
a sorting algorithm specifically for an array of integers
what is a bucket
a collection of integer values that all share a particular digit value
how do buckets relate to radix sort?
the algorithm makes use of buckets and is a type of bucket sort
what is a fast sorting algorithm?
a sorting algorithm that has an average runtime complexity of O(NlogN) or better
what is an element comparison sorting algorithm?
a sorting algorithm that operates on an array of elements that can be compared to each other
explain insert algorithm for heaps
An insert into a max-heap starts by inserting the node in the tree’s last level, and then swapping the node with its parent until no max-heap property violation occurs. Inserts fill a level (left-to-right) before adding another level, so the tree’s height is always the minimum possible. The upward movement of a node in a max-heap is called percolating.
explain remove algorithm for heaps
A remove from a max-heap is always a removal of the root, and is done by replacing the root with the last level’s last node, and swapping that node with its greatest child until no max-heap property violation occurs. Because upon completion that node will occupy another node’s location (which was swapped upwards), the tree height remains the minimum possible.
