Brainscape's Knowledge GenomeTM

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


See full index

CS YEAR ONE > DSA - Priority Queue & Heap Trees > Flashcards

DSA - Priority Queue & Heap Trees Flashcards

1
Q

Define Priority Queue:

A
  • Abstract Data Type that maintains a collection of item which has an associated priority value
  • Gets & removes the items with highest priority efficiently
  • Items with arbitrary values can be added at any time
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Name the 3 ways to implement Priority Queue:

A
  • Unsorted Array
  • Sorted Array
  • AVL tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Complexity of Priority Queue using Unsorted Array?

A
  • Inserting an item is O(1)
  • get is O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Complexity of Priority Queue using Sorted Array?

A
  • Inserting an item is O(n)
  • get is O(1)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Complexity of Priority Queue using AVL Tree ?

A
  • Insert & Get is O(log(n))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How are Elements sorted in AVL tree for Priority Queue?

A
  • Sort Elements using Priority Value
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Explain What Binary Heap Tree is?

A

A binary tree is a BHT if it is Complete meaning that every level except last is COMPLETELY FILLED & all leaves are placed as far to the left as possible

  • Binary with the a given number of nodes, the tidiest, most balanced and compact possible
  • DOES NOT requirements for BST
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How do we Implement Priority Queue as A BHT?

A

Using an ARRAY
- Place Nodes in the array Root, Left Child then right

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

IF Binary Tree is NOT COMPLETE?

A
  • Wasteful implementation strategy because space is still reserved for missing nodes
  • Array cell need to be marked to indicate that it is not part of tree

MUST use ;
- Invalid values for this application
- Separate data structure to indicate whether the corresponding cell contains a real value

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

IF Binary Tree is COMPLETE?

A
  • Tree is sufficient to identify the END of the TREE
  • Not need to mark missing nodes because none before the end of the tree are missing
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

DEFINITION of BHT

A

COMPLETE Binary Tree which is either empty or Satisfies the following conditions;

  • Priority of the root is greater or equal to that of its children
  • Left & Right subtrees of the root are Heap Trees
  • NO Restriction on the relationship between the left & right children of any Node

NO NEED TO SORT BHT

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

IDEA of BHT Insertion?

A

Insert the value at the end of the last level and then keeps bubbling up as long as it is larger than its parent

AS we bubble up, when we swap the value of a node i with that of its parent, don’t compare i with sibling as if it is larger than parent must be larger than sibling

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

What is Worst case for BHT insertion?

A

Bubbling to the Root which is log(n) operations

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

What is the idea of Deleting the ROOT?

A

1- Remove the last RIGHTMOST node and replace it with ROOT
2- Bubble down:
-keep swapping it with the higher priority child as long as
any of its children have HIGHER PRIORITY

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

What is the idea of Deleting an Arbitrary node?
(DELETING an NODE Anywhere)

A

1- Remove the last RIGHTMOST node and replace it with the node to be Deleted
2- Node may be smaller or Larger than the Children thus Bubble UP or DOWN where necessary, DO BUBBLE UP THEN BUBBLE DOWN
– NEED TO CHECK WHICH METHOD IT SHOULD DO

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

Code for Inserting?

A

public void insert ( int p ) {
if ( n == MAXSIZE )
throw HeapFullException ;
n = n + 1 ;
heap [ n ] = p ;
//insert the new value as the last
// node o f t h e l a s t l e v e l
bubbleUp ( n ) ; // and b u b b l e i t up
}

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

Idea of Bubble Up?

A
  • check if ur at rook by checking if i ==1
  • otherwise check whether heap(i) is greater than heap(parent(i))
    if so swap and them around and call bubble up again
  • else return Heap tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Idea of Bubble Down?

A
  • Check if root has no children by doing left(i) > n, if true return tree
  • Then check if it has one Child LEFT do right(i)>n
    if Left child is greater than heap(i) then swap them and return tree
  • Otherwise there a 2 Children:
    First Check Left is Greater than Right child then check if Left is Greater than heap(i), if so swap and then Bubble Down left(i)
  • Else Right is greater :
    Check if right is greater than heap(i), if so swap and then bubble down left(i)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How do you represent heap value for left(i) in BUBBLE DOWN?

A

heap[left(i)]

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

How do you represent heap value for right(i) in BUBBLE DOWN?

A

heap[right(i)]

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

How do you represent heap value for parent in BUBBLE UP?

A

heap[parent(i)]

21
Q

What is Update in BHT?

A

-Modifying the priority of element in tree

22
Q

Idea of Update?

A
  • Change value of heap(i)
  • bubbleUp(i) & bubbleDown(i) to make sure it is in correct position
  • Need to make sure tree is not empty /n < 1
  • Need to make sure i is in bounds not <1 or >n
23
Q

How do we build Build a Binary Heap Tree using items in an array IN RANDOM ORDER?

A
  • ALREADY have it in complete Binary Tree Form
  • NOT In BHT Form
  • Currently all leaf nodes satisfy the heap tree properties, just no internal nodes
  • Therefore we iterate over internal nodes staring with last and work up to first calling BUBBLEDOWN each time
  • Each time ensure that the subtree based on node become a valid BHT, Thus at end whole tree is valid BHT
  • Last node n parent is n/2, must be last internal node {because n/2+1 would have a left child 2*n/2+1 = n+2 which doesn’t exist, so n/2+1 is not a internal node}
24
Q

Idea of Heapify in the array based BHT scenario

A

-So for all internal nodes, including root node you will bubble down each of them so they are in correct order

  • Start with n/2 (last INTERNAL NODE)
  • End with root or where i = 1
  • i must be >0
25
Q

Complexity of Heapify ?

A

h is height of heap tree, root node need to swap h-many node, nodes on level 1 must make h-1 swap and so on

WORST CASE:
C(h) = h+2(h-1)+4(h-2)+…+(2^(h-1))(h-(h-1))
= h+2(h-1)+4(h-2)+…+(2^(h-1))(1)
=>∑2^i(h-1) = 2^h/2^h ∑2^i(h-1) = 2^h ∑ h-i/((2^h)-i)

=> 2^h ∑ {i<= h} j/2^j <= 2^h ∑ {i<= ∞} j/2^j

2^h ∑ {i<= ∞} j/2^j == 2 we get
C(h) = 2*2^h = 2^h+1

So Complexity = O( 2^h+1) = O(2^h) = O(n)

26
Q

How to Merge BHTs Method 1 ?

A

1) Insert each item of 1 tree into the other
- n inserts, hence O(nlog(n))

27
Q

How to Merge BHTs Method 2 ?

A

2) Remove the last elements of the bigger tree & insert them into the smaller until the tree made from DUMMY ROOT NODE & the Smaller & Bigger Trees as its left and Bigger as right child. Standard Delete method to delete the Dummy Root node

    - AVG, smaller Tree is 1/2 of the size of the 
      larger, 1/4 of leaf nodes of large must be 
      inserted into the smaller to make them 
      approx equal in size, so O(n) inserts, thus 
      complexity is O(nlog(n)). But will be 1/4 of the 
      no. of operations of previous methods so 
      faster.
  • NEW ROOT Swap with Rightmost leaf node , then bubbleDown so entire tree holds original value
28
Q

How to Merge BHTs Method 3 ?

A

3) Concatenate the array forms & call Heapift
- O(n)

29
Q

What are the 3 Major Approaches to Merge 2 BHTs of similar size n:

A

1) Insert each item of 1 tree into the other
- n inserts, hence O(nlog(n))

2) Remove the last elements of the bigger tree & insert them into the smaller until the tree made from DUMMY ROOT NODE & the Smaller & Bigger Trees as its left and Bigger as right child. Standard Delete method to delete the Dummy Root node

3) Concatenate the array forms & call Heapify
- O(n)

30
Q

What is a Binomial Tree?

A
  • A binomial tree of order 0 is a single node
  • a binomial tree of order k has a root node with children that are roots of binomial trees of orders
    k-1,k-2,…,2,1,0
  • Binomial tree of order k has exactly 2^k nodes
31
Q

How can a Binomial Heap tree of order k be constructed by 2 trees?

A

2 Trees of order k-1 by attaching one of them as a new Leftmost child of the root of the other

==> This is the basis of the efficient merge operation for binomial heaps

32
Q

How are Binomial Heaps Trees Connected?

A

Connected by a Linked List, Usually a Doubly LL

33
Q

How to pick where we start for our Binomial Tree?

A

Look at the Root nodes to find where to start
- Linear Search between ROOTS

34
Q

What makes Binomial Heap Tree worst case?

A

No. of nodes each double consecutive tree there will be log(n) trees requires to store n values, so this is O(log(n))

35
Q

Example of merge table?

A

Order|Carry-in|H1|H2|Out|Carry-Out

36
Q

What doe u do with H1&H2?

A

If they are the same order then merge them and put it as carry-out, leave Out empty unless there is only 1 tree of that order then we put it in output.

THE CARRY-OUT IS USED FOR CARRY-IN FOR WHEN YOU CHEK THE NEXT ORDER

37
Q

What is the Output tree called?

A

Resulting Tree

38
Q

Complexity of Binomial Trees?

A
  • Merge 2 Binomial Trees is O(1)
  • Merge 2 Binomial Heap Trees is O(log(n))
  • Inserting merges 2 Binomial Heaps:
    - Equal chance of having Order 0 branch
    • (1/2)^2 the other heap has BT of order 1 & requires merge

FULL AVERAGE AMORTISED COST OF INSERTION:
O(1) *∑{i<= ∞} (1/2)^i = O(1) ON AVG.

O(1) = 1/2+1/4+1/8+… ≈ 1

39
Q

What is Binomial Heap Tree?

A
  • Each node has a priority less than or equal to its parent
    -Only 0 or 1 of each order
40
Q

What are the 4 possible Outputs of Binomial Heap?

A

1) NO output Tree of order k or carry out of k+1

2) There is an output Tree of order k but there is no carry out of k+1

3) NO output Tree of order k or carry out of k+1

4) Output tree of order k is one of input tree (Carry out of k-1) & the carry-out k+1 is merge of the other 2 input trees

41
Q

What is Complexity of Building a Binomial Heap from a collection of n value?

A

O(n)
- Insert n times

42
Q

Change the Priority of a node in Binomial Heap Complexity?

A

O(log n)
- bubbleUp / bubbleDown processes similar to Binary heaps

43
Q

Deleting Highest Priority Node?

A

O(logn) + O(logn) = O(logn)
- Linear search through the roots of Binomial tee is O(logn)
- Removing the root node & merging the subtree back into Binomial Heap is O(logn).

44
Q

Deleting non-root nodes?

A

O(logn)
Setting the node’s priority to ∞ and bubble it up to root and delete it similar to Deleting Highest Priority Node

45
Q

Difference between Binomial and Fibonacci Heaps?

A
  • Similar that Binomial & Fibonacci are collection of trees
  • But have different constraints on their structure
  • More complex than Binomial Heaps, make use of lazy modifications to keep themselves

-Fibonacci advantage over Binomial Heap are that they complexity of O(1) for merge, & Updating the priority of node has amortised complexity of O(1)

46
Q

Complexity for all Operation of Binary Heaps?

A
  • Insert : O(logn)
  • Delete: O(logn)
  • Update: O(logn)
  • Merge: O(n)
  • Heapify: O(n)
47
Q

Complexity for all Operation of Binomial Heaps?

A
  • Insert : O(1) // AMORTIZED
  • Delete: O(logn)
  • Update: O(logn)
  • Merge: O(logn)
  • Heapify: O(n)
48
Q

Complexity for all Operation of Fibonacci Heaps?

A
  • Insert : O(1) // AMORTIZED
  • Delete: O(logn) // AMORTIZED
  • Update: O(1) // AMORTIZED
  • Merge: O(1)
  • Heapify: O(n)
49
Q

Explain why Binary heap complexity is O(log n)

A

Binary heap tree is O(log n), where n is the number of nodes of the binary heap tree. This is because the insertion takes O(log n), since it requires traversing from the root down to a leaf in a well balanced tree, and the bubble-up takes time at most the height of the tree, which ,for a well balanced tree with n nodes equals at most log n

CS YEAR ONE (15 decks)

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