Skip to main content

applications-of-heap

· One min read

slug: heap-application title: Applications of Heap tags: [data structure, heap]​

leetcode natively supports JS PQs, including a Min one.

github datastructures - priority queue

github leetcode - environment for the programming languages

Use the Heap data structure to obtain Top K’s largest or smallest elements.

Solution of the Top K largest elements:

  1. Construct a Max Heap.
  2. Add all elements into the Max Heap.
  3. Traversing and deleting the top element, and store the value into the result arry T.
  4. Repeat step 3 until we have removed the K largest elements.

Solution of the Top K smalllest elements

  1. Construct a Min Heap
  2. Add all elements into the Min Heap
  3. Traversing and deleing the top element, and store the value into the result array T.
  4. Repeat step 3 until we have removed the K smallest elements.

Time Complexity: O(KlogN + N) Space complexity: O(N)