Priority Queue interface

1
2
3
4
5
6
public interface MinPQ<item>{
	public void add(Item x);
	public Item getSmallest();
	public Item removeSmallest();
	public int size();
}

Task: use the interface to track the M best
core code:

1
if(unharmoniousTests.size() > M) unharmoniousTests.removeSmallest();

perfect implementation–heap

Heap

We will define our binary min-heap as being complete and obeying min-heap property:

  • Min-heap: Every node is less than or equal to both of its children
  • Complete: Missing items only at the bottom level (if any), all nodes are as far left as possible.
    ![[Pasted image 20240427225515.png]]
    image (1536×355) (gitbook.io)
    The green ones are correct min-heaps and red ones are not.
    we can see that as the root is smaller than all its children, it is smaller than anyone in the queue.

Implementation

getSmallest: return the root node
add:

  1. add the element to the bottom left position
  2. exchange it with the upper ones to ensure the characters
    removeSmallest: remove the root, and then move the element on the bottom to the top, then exchanging

Tree implementation in Java

1. create map from parent to children

1.1.
![[Pasted image 20240428142605.png]]

1
2
3
4
5
6
public class Tree1A<Key>{
Key k;
Tree1A left;
Tree1A middle;
Tree1A right;
}

1.2.
![[Pasted image 20240428142731.png]]

1
2
3
4
5
public class Tree1B<Key>{
Key k;
Tree1B[] children;
...
}

1.3.
![[Pasted image 20240428142927.png]]

1
2
3
4
5
6
public class Tree1C<Key>{
Key k;
Tree1C children;
Tree1C sibilings;
...
}

store keys in an array(similar to that in union-find sets)

![[Pasted image 20240428143407.png]]

store keys in an array. Do not store structures

only works for complete trees

1
2
3
4
5
6
7
8
9
10
11
public void swim(int k)
{
	if (keys[parent(k)] > keys[k]) {
		swap(k, parent(k));
		swim(parent(k));
	}
}

public int parent(int k) {
	return (k-1) / 2;
}

3.2(book implementation):
Store keys in an array. Offset everything by 1 spot.

  • leave spot 0 empty.
  • make computation of parents and kids easier.
    complexity for each Implementation of PQs:
    ![[Pasted image 20240428151149.png]]
    memory complexity, code simplexity considered, heap is the easiest one.
    Summary: search data structures
    ![[Pasted image 20240428152036.png]]