Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS 3345 > Binary Heaps and Binomial Heaps > Flashcards

Binary Heaps and Binomial Heaps Flashcards

1
Q

What happens to the key values along any path from the root to a leaf?

A

They are increasing, or a duplicate is encountered.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Reversed

An array of objects that are comparable.

The size of the array(how many objects are in it).

A

What are the two data variables in the BinaryHeap class?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How do Binomial Queues differ from Binary heaps?

A

It is not a heap-ordered tree but rather a collection of heap-ordered trees known as a forest.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What kind of binary tree is a heap?

A

It is a complete Binary Tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Reversed

at 2i

A

In a binary heap, where is the left child of the parent at i located?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How does Heap Sort work?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Reversed

They are increasing, or a duplicate is encountered.

A

What happens to the key values along any path from the root to a leaf?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the runtimes of Binomial Queues?

A

insert, deleteMin, and merging are O(Log N) worst case, but on average, inserts take constant time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How is a binomial tree Bk formed?

A

By attaching two binomial trees, Bk-1 and Bk-1 together.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Reversed

A b0 tree, a b3 tree, and a b6 tree.

A

How many Bi top level trees exist in a Binomial heap containing 73 values?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

A complete binary tree of height h has how many nodes?

A

Between 2h and 2h+1-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is different about the MaxHeap?

A

It includes a deleteMax(), instead of a deleteMin()

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Reversed

a data structure that allows at least the operations of insert and deleteMin.

A

What is a priority queue?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the 9 methods Included in the BinaryHeap Class?

A
  1. 3 constructors
  2. FindMin
  3. DeleteMin
  4. Insert
  5. PercolateDown
  6. isEmpty
  7. MakeEmpty
  8. EnlargeArray
  9. BuildHeap
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does the decreaseKey operation do?

A

It takes a keyLocation and amount to decrease the key by, then the node is percolated up to its new correct location.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Show the result of performing three deleteMin operations on the following Binomial heap.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the percolate down algorithm?

A
  • 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;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the runtime of FindMin()?

A

It takes constant time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Each node in a binomial tree has references to what?

A

To its first child, and next sibling.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

How many Bi top level trees exist in a Binomial hep containing 173 values?

A

A b0 tree, a b2 tree, a b3 tree, a b5 tree, a b7 tree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the delteMin algorithm?

A
  • Object deleteMin()
    • if(isEmpty()) throw error;
    • Object Min = array[1];
    • array[1] = array[currentSize–];
    • percolateDown(1);
    • return MinItem;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

A Bk Binomial tree consists of what?

A

A Bk tree contains each of the trees B0, B1, …Bk-1 trees, plus an extra B0 that forms the root of the tree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Reversed

It begins at the penultimate level.

A

Where does the buildHeap function begin?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Reversed

A b0 tree, a b2 tree, a b3 tree, a b5 tree, a b7 tree.

A

How many Bi top level trees exist in a Binomial hep containing 173 values?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

How many trees are in any binomial queue containing N nodes?

A

The number of trees is ≤ Log N

27
Q

What is a priority queue?

A

a data structure that allows at least the operations of insert and deleteMin.

28
Q

Reversed

It takes constant time.

A

What is the runtime of FindMin()?

29
Q

Reversed

At index 1.

A

At what index does a binary Heap begin in the array?

30
Q

What is the MinHeap Property?

A

For any node containing key x, the keys in both the left and right subtrees of that node are all larger than x.

31
Q

What does deleteMin do?

A

returns the minimum valued element and deletes it from the queue.

32
Q

Reversed

returns the minimum valued element and deletes it from the queue.

A

What does deleteMin do?

33
Q

What is the percolate up strategy?

A

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.

34
Q

How many Bi top level trees exist in a Binomial heap containing 73 values?

A

A b0 tree, a b3 tree, and a b6 tree.

35
Q

What is the height of a complete binary tree?

A

The floor of Log N

36
Q

How does deleteMin work on a Binomial queue?

A

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.

37
Q

Merging binary trees follows what kind of rules?

A

Merging Binary trees follows the rules of Binary arithmetic.

38
Q

How are two trees of the same degree merged?

A

By making the tree with the larger root key the left subtree of the other tree.

39
Q

At what index does a binary Heap begin in the array?

A

At index 1.

40
Q

GIve the code for binaryHeap(items[])

A
  • BinaryHeap(items[])
    • currentSize = items.length;
    • array = new array[(currentSize+2)*11/10]
    • int i =1;
    • for(item: items)
      • array[i++]= item;
    • buildHeap();
41
Q

In a binary heap, where is the parent of a node at i located?

A

at the floor of i/2

42
Q

How do we do insertion into a Binomial queue?

A

We just do a merge of a B0 tree consisting of the new node

43
Q

What are the two data variables in the BinaryHeap class?

A

An array of objects that are comparable.

The size of the array(how many objects are in it).

44
Q

A binomial tree Bk contains how many nodes?

A

2k

45
Q

What is the running time for buildHeap?

A

O(N)

46
Q

In a binary heap, where is the left child of the parent at i located?

A

at 2i

47
Q

How do we use a binary heap to solve the selection sort problem?

A

We read N elements into an array

We buildHeap on the array

We perform k delteMins to find the kth smallest element.

48
Q

What is a D-heap?

A

a binary heap except that all nodes have d children.

49
Q

What is the constraint on Binomial trees in Binomial queues?

A

There is at most one binomial tree of every height.

50
Q

Where does the buildHeap function begin?

A

It begins at the penultimate level.

51
Q

What is the most common priority queue implementation?

A

The Binary Heap

52
Q

What is the insert algorithm for a BinaryHeap?

A
  • 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;
53
Q

Reversed

at 2i + 1

A

In a binary heap, where is the right child of the node at i located?

54
Q

Reversed

It is a complete Binary Tree

A

What kind of binary tree is a heap?

55
Q

What is the Binary Heap topology rule?

A

All levels of the binary heap are full, with the possible exception of the last level, which fills from left to right.

56
Q

How do greedy Algorithms operate?

A

By repeatedly finding a minimum.

57
Q

What is the build heap algorithm?

A
  • buildHeap()
    • for(int i =currentSize/2; i >0; i–) percolateDown(i);
58
Q

What is the worst case runtime for delete and insert on a binaryHeap?

A

log N

59
Q

In a binary heap, where is the right child of the node at i located?

A

at 2i + 1

60
Q

Reversed

The Binary Heap

A

What is the most common priority queue implementation?

61
Q

What does a Binomial queue mostly consist of?

A

An array of references that point to the root nodes of the trees that make up a Binomial queue.

62
Q

Reversed

at the floor of i/2

A

In a binary heap, where is the parent of a node at i located?

63
Q

Reversed

By repeatedly finding a minimum.

A

How do greedy Algorithms operate?

CS 3345 (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions