Implementing heaps

Date: April 8, 2023

Topic: Heap & Graph Search Algorithms

Recall

Heap intro

Question

Q1 Find smallest kth elements form an unsorted array(size n)

Representation of graph

图里常见的search

经典例题BFS-1：Level order

get Keys in binary tree layer by layer

Notes

• Heap: 维护一个变化的数据集的最优值
• 性质：Heap的实现通过构造二叉堆
  • Heap总是一棵完全二叉树
  • 任意节点小于等于它的后裔(descendent)堆序性
• 根节点最小的叫做MinHeap，反之MaxHeap
• implemented as an unsorted array
  • index of lchild: my index * 2 + 1;
  • index of rchild: my index * 2 + 2;
  • index of parent: (my index - 1) / 2;

• Solution 1: MinHeap

  • Step 1: Heapify all elements → O(constant * n)
  • Step2: call pop( ) k times to get the k smallest elements → O(k* logn)
  • TC: O(constant * n + k * logn)

• Solution 2: MaxHeap

• Step 1: Heapify the first k elements to form a MaxHeap of size = k. O(k)

• Step 2: Iterate over the remain elements one by one. O((n-k) * logk)

• TC: O(k + (n - k) * logk)

• Adjacency matrix

• Adjacency list O(V)

• HashMap<Node, Set<Node>>

• List<GraphNode>: O(v)

Breadth First Search BFS -1

• Data structure: Maintain a FIFO queue
• Initial State
• Expand: poll from queue
• Generate neighbor nodes: insert into queue
• Termination condition:
  • queue is empty
  • when conflict is found
  • when the target node is expanded
  • when the k-th element is expanded
• Optionally deduplicate visited nodes (typically for graph not for tree)

• 用了一个LinkedList implement 的queue装root，每一次往里面放一层，用当前queue的size来确保每个TreeNode都被遍历了一遍，且用两个if确保左右子树都被装进了curLayer。

public class solution {
	public List<List<Integer>> LayerByLayer(TreeNode root) {
		List<List<Integer>> list = new ArrayList<>();
		if (root == null) {
			return list;
		}
		//用一个queue来装整棵树
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			List<Integer> curLayer = new ArrayList<>();
			int size = queue.size;
			for (int i = 0; i < size; i++) {
				TreeNode cur = queue.poll();
				curLayer.add(cur.key);
				if (cur.left != null) {
					queue.offer(cur.left);
				}
				if (cur.right != null) {
					queue.offer(cur.right);
				}
			}
			list.add(curLayer);
		}
		return list;
}
TC: O(n)
SC: O(n)

Best First Search (BFS - 2)

• Data structure: Priority_queue(MIN_HEAP)
• Initial State (Start node)
• Expand: poll from queue
• Generate neighbor nodes: insert into queue
• Termination condition: do a loop until the p_queue is empty
• deduplicate: expanded each node only once(typically for graph not for tree)

<aside> 💡 dijkstra’s algorithm 的重要性质

• one node can be expanded once and only once
• one node can be generated more than once.(cost can be reduced over time)
• all the cost of the nodes that are expanded are monotonically non-decreasing (所有从priority_queue里面pop出来的元素的值是单调非递减—> 单调递增）
• when a node is popped out for expansion, its value is fixed which is equal to the shortest distance from the start node.
• time complexity, for a graph with n nodes and the connectivity of the node is constant O(n log n) for a general graph. </aside>

<aside> 📌 SUMMARY:

</aside>

Date: April 8, 2023

Topic: Heap in Java（PriorityQueue）

Recall

K Smallest in unsorted Array

Notes

• definition

• It's a heap with the same Queue interface with offer(), peek(), and poll()

• But it’s not FIFO, when poll() or Peek() we always look at the smallest or largest element

• 内存里存放方法：array

• 对应Java class：Priority Queue

• 对应Interface： Queue

• Method 1: MaxHeap

• Method 2: MinHeap

两种方式provide a comparator class or set class with natural ordering

• Use interface Comparable and @ Override compareTo(E e)method

public int compareTo(Integer anotherInt)
return:
- 0,两者相等
- -1, this.Integer < anotherInt
- 1, this.Integer > anotherInt

eg. Integer a = new Integer(10);
    Integer b = new Integer(20);
Ststem.out.println(a.compareTo(b));  -1;

Declaration: PriorityQueue<MyInteger> pq = new PriortyQueue<>( );

• Interface Comparator and override Compare(E e1, E e2) method

<aside> 📌 SUMMARY:

</aside>

Date: April 9, 2023

Topic: Practice 10 Implementing Heaps

<aside> 📌 SUMMARY:

</aside>