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)

<aside> 📌 SUMMARY:

</aside>

Date: April 8, 2023

Topic: Heap in Java（PriorityQueue）

<aside> 📌 SUMMARY:

</aside>

Date: April 9, 2023

Topic: Practice 10 Implementing Heaps

<aside> 📌 SUMMARY:

</aside>