DSA - Priority Queue & Heap Trees

Question 1

Define Priority Queue:

Answer 1

• 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

Question 2

Name the 3 ways to implement Priority Queue:

Answer 2

• Unsorted Array
• Sorted Array
• AVL tree

Question 2

Complexity of Priority Queue using Unsorted Array?

Answer 2

• Inserting an item is O(1)
• get is O(n)

Question 3

Complexity of Priority Queue using Sorted Array?

Answer 3

• Inserting an item is O(n)
• get is O(1)

Question 4

Complexity of Priority Queue using AVL Tree ?

Answer 4

• Insert & Get is O(log(n))

Question 5

How are Elements sorted in AVL tree for Priority Queue?

Answer 5

• Sort Elements using Priority Value

Question 6

Explain What Binary Heap Tree is?

Answer 6

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

Question 7

How do we Implement Priority Queue as A BHT?

Answer 7

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

Question 8

IF Binary Tree is NOT COMPLETE?

Answer 8

• 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

Question 9

IF Binary Tree is COMPLETE?

Answer 9

• 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

Question 10

DEFINITION of BHT

Answer 10

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

Question 11

IDEA of BHT Insertion?

Answer 11

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

Question 12

What is Worst case for BHT insertion?

Answer 12

Bubbling to the Root which is log(n) operations

Question 13

What is the idea of Deleting the ROOT?

Answer 13

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

Question 14

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

Answer 14

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

Question 15

Code for Inserting?

Answer 15

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
}

Question 16

Idea of Bubble Up?

Answer 16

• 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

Question 17

Idea of Bubble Down?

Answer 17

• 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)

Question 18

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

Answer 18

heap[left(i)]

Question 19

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

Answer 19

heap[right(i)]

Question 20

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

Answer 20

heap[parent(i)]

Question 21

What is Update in BHT?

Answer 21

-Modifying the priority of element in tree

Question 22

Idea of Update?

Answer 22

• 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

Question 23

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

Answer 23

• 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}

Question 24

Idea of Heapify in the array based BHT scenario

Answer 24

-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

Question 25

Complexity of Heapify ?

Answer 25

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)

Question 26

How to Merge BHTs Method 1 ?

Answer 26

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

Question 27

How to Merge BHTs Method 2 ?

Answer 27

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

Question 28

How to Merge BHTs Method 3 ?

Answer 28

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

Question 29

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

Answer 29

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)

Question 30

What is a Binomial Tree?

Answer 30

- 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

Question 31

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

Answer 31

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

Question 32

How are Binomial Heaps Trees Connected?

Answer 32

Connected by a Linked List, Usually a Doubly LL

Question 33

How to pick where we start for our Binomial Tree?

Answer 33

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

Question 34

What makes Binomial Heap Tree worst case?

Answer 34

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

Question 35

Example of merge table?

Answer 35

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

Question 36

What doe u do with H1&H2?

Answer 36

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

Question 37

What is the Output tree called?

Answer 37

Resulting Tree

Question 38

Complexity of Binomial Trees?

Answer 38

- 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

Question 39

What is Binomial Heap Tree?

Answer 39

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

Question 40

What are the 4 possible Outputs of Binomial Heap?

Answer 40

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

Question 41

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

Answer 41

O(n) - Insert n times

Question 42

Change the Priority of a node in Binomial Heap Complexity?

Answer 42

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

Question 43

Deleting Highest Priority Node?

Answer 43

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).

Question 44

Deleting non-root nodes?

Answer 44

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

Question 45

Difference between Binomial and Fibonacci Heaps?

Answer 45

- 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)

Question 46

Complexity for all Operation of Binary Heaps?

Answer 46

- Insert : O(logn) - Delete: O(logn) - Update: O(logn) - Merge: O(n) - Heapify: O(n)

Question 47

Complexity for all Operation of Binomial Heaps?

Answer 47

- Insert : O(1) // AMORTIZED - Delete: O(logn) - Update: O(logn) - Merge: O(logn) - Heapify: O(n)

Question 48

Complexity for all Operation of Fibonacci Heaps?

Answer 48

- Insert : O(1) // AMORTIZED - Delete: O(logn) // AMORTIZED - Update: O(1) // AMORTIZED - Merge: O(1) - Heapify: O(n)

Question 49

Explain why Binary heap complexity is O(log n)

Answer 49

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