Binary Heaps and Binomial Heaps Flashcards
What happens to the key values along any path from the root to a leaf?
They are increasing, or a duplicate is encountered.
Reversed
An array of objects that are comparable.
The size of the array(how many objects are in it).
What are the two data variables in the BinaryHeap class?
How do Binomial Queues differ from Binary heaps?
It is not a heap-ordered tree but rather a collection of heap-ordered trees known as a forest.
What kind of binary tree is a heap?
It is a complete Binary Tree
Reversed
at 2i
In a binary heap, where is the left child of the parent at i located?
How does Heap Sort work?
Heap sort begins with a Max Heap data structure. An array is sent to the constructor which builds the heap. DeleteMax is repeatedly called and stores the result in the array until the heap is empty.
Reversed
They are increasing, or a duplicate is encountered.
What happens to the key values along any path from the root to a leaf?
What are the runtimes of Binomial Queues?
insert, deleteMin, and merging are O(Log N) worst case, but on average, inserts take constant time.
How is a binomial tree Bk formed?
By attaching two binomial trees, Bk-1 and Bk-1 together.
Reversed
A b0 tree, a b3 tree, and a b6 tree.
How many Bi top level trees exist in a Binomial heap containing 73 values?
A complete binary tree of height h has how many nodes?
Between 2h and 2h+1-1
What is different about the MaxHeap?
It includes a deleteMax(), instead of a deleteMin()
Reversed
a data structure that allows at least the operations of insert and deleteMin.
What is a priority queue?
What are the 9 methods Included in the BinaryHeap Class?
- 3 constructors
- FindMin
- DeleteMin
- Insert
- PercolateDown
- isEmpty
- MakeEmpty
- EnlargeArray
- BuildHeap
What does the decreaseKey operation do?
It takes a keyLocation and amount to decrease the key by, then the node is percolated up to its new correct location.
Show the result of performing three deleteMin operations on the following Binomial heap.
What is the percolate down algorithm?
- percolateDown(int Hole)
- int child;
- Object tmp = array[hole];
- for( ; hole*2< = currentSize; hole = child)
- child = hole*2;
- if(child ≠ currentSize && array[child] < array[child+1]) child++;
- if(array[child].compareTo(tmp) < 0) array[hole] = array[child];
- else: break;
- array[hole] = tmp;
What is the runtime of FindMin()?
It takes constant time.
Each node in a binomial tree has references to what?
To its first child, and next sibling.
How many Bi top level trees exist in a Binomial hep containing 173 values?
A b0 tree, a b2 tree, a b3 tree, a b5 tree, a b7 tree.
What is the delteMin algorithm?
- Object deleteMin()
- if(isEmpty()) throw error;
- Object Min = array[1];
- array[1] = array[currentSize–];
- percolateDown(1);
- return MinItem;
A Bk Binomial tree consists of what?
A Bk tree contains each of the trees B0, B1, …Bk-1 trees, plus an extra B0 that forms the root of the tree.
Reversed
It begins at the penultimate level.
Where does the buildHeap function begin?
Reversed
A b0 tree, a b2 tree, a b3 tree, a b5 tree, a b7 tree.
How many Bi top level trees exist in a Binomial hep containing 173 values?
Show the result of inserting the sequence of values 10, 21, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2 into an initially empty binomial queue
How many trees are in any binomial queue containing N nodes?
The number of trees is ≤ Log N
What is a priority queue?
a data structure that allows at least the operations of insert and deleteMin.
Reversed
It takes constant time.
What is the runtime of FindMin()?
Reversed
At index 1.
At what index does a binary Heap begin in the array?
What is the MinHeap Property?
For any node containing key x, the keys in both the left and right subtrees of that node are all larger than x.
What does deleteMin do?
returns the minimum valued element and deletes it from the queue.
Reversed
returns the minimum valued element and deletes it from the queue.
What does deleteMin do?
What is the percolate up strategy?
an empty node is created in the first available location (the last element in an array). While the key in the parent node is larger than the key to be inserted, the parent node is moved down to the empty node, and the parent node becomes the empty node.
How many Bi top level trees exist in a Binomial heap containing 73 values?
A b0 tree, a b3 tree, and a b6 tree.
What is the height of a complete binary tree?
The floor of Log N
How does deleteMin work on a Binomial queue?
The roots are scanned and the lowest is returned. All of the children of that node are separated as separate binomial trees, which are then merged back into the binomial heap.
Merging binary trees follows what kind of rules?
Merging Binary trees follows the rules of Binary arithmetic.
How are two trees of the same degree merged?
By making the tree with the larger root key the left subtree of the other tree.
At what index does a binary Heap begin in the array?
At index 1.
GIve the code for binaryHeap(items[])
- BinaryHeap(items[])
- currentSize = items.length;
- array = new array[(currentSize+2)*11/10]
- int i =1;
- for(item: items)
- array[i++]= item;
- buildHeap();
In a binary heap, where is the parent of a node at i located?
at the floor of i/2
How do we do insertion into a Binomial queue?
We just do a merge of a B0 tree consisting of the new node
What are the two data variables in the BinaryHeap class?
An array of objects that are comparable.
The size of the array(how many objects are in it).
A binomial tree Bk contains how many nodes?
2k
What is the running time for buildHeap?
O(N)
In a binary heap, where is the left child of the parent at i located?
at 2i
How do we use a binary heap to solve the selection sort problem?
We read N elements into an array
We buildHeap on the array
We perform k delteMins to find the kth smallest element.
What is a D-heap?
a binary heap except that all nodes have d children.
What is the constraint on Binomial trees in Binomial queues?
There is at most one binomial tree of every height.
Where does the buildHeap function begin?
It begins at the penultimate level.
What is the most common priority queue implementation?
The Binary Heap
What is the insert algorithm for a BinaryHeap?
- insert(Object x)
- if(currentSize == array.length-1) enlargeArray(array.length*2+1)
- int hole = ++currentSize;
- for(array[0] = x; x.compareTo(array[hole/2]) < 0; hole/=2)
- array[hole] = array[hole/2]
- array[hole] = x;
Reversed
at 2i + 1
In a binary heap, where is the right child of the node at i located?
Reversed
It is a complete Binary Tree
What kind of binary tree is a heap?
What is the Binary Heap topology rule?
All levels of the binary heap are full, with the possible exception of the last level, which fills from left to right.
How do greedy Algorithms operate?
By repeatedly finding a minimum.
What is the build heap algorithm?
- buildHeap()
- for(int i =currentSize/2; i >0; i–) percolateDown(i);
What is the worst case runtime for delete and insert on a binaryHeap?
log N
In a binary heap, where is the right child of the node at i located?
at 2i + 1
Reversed
The Binary Heap
What is the most common priority queue implementation?
What does a Binomial queue mostly consist of?
An array of references that point to the root nodes of the trees that make up a Binomial queue.
Reversed
at the floor of i/2
In a binary heap, where is the parent of a node at i located?
Reversed
By repeatedly finding a minimum.
How do greedy Algorithms operate?
