Here are the summaries for the Heap algorithms in Leetcode's Blind 75. Check out the previous post on Dynamic Algorithms. A Binary Heap is a type of Binary Tree, specifically a complete Binary Tree (where all levels are filled except the lowest level), which is used to store data efficiently to get the max or min element based on its type.

Merge K Sorted Lists

This was already included in the List topic.

Top K Frequent Elements

Given an integer array nums of length n and an integer k, return the k most frequent elements.

Solution with O(n*Log(k)) time / O(n) space

This is a two part solution:

1. Iterate through nums, constructing a map of the [integer values] → [count of the value in the array] (i.e. group integers by count).
2. Using a min priority queue (this example uses a heap for time complexity calculations) of the grouping map above, prioritized based on the count value:
3. Iterate through the grouping map above, adding each element to the queue. If the size of the queue exceeds k, remove the element with the lowest count.

The key of the elements left in the queue is the answer.

Find Median from Data Stream

Implement the MedianFinder class which has two methods:

1. Add a number to the data set.
2. Find the median value (if the size of the data set is even, then find the mean of the two middle values).

Solution with O(Log(n)) time to add, O(1) time to find the median / O(n) space

We’ll use two priority queues, one to store the numbers from the lower half, the other to store the numbers from the higher half.

When adding the number to the data set we need to make sure the number is added to the correct queue, and the queues should have sizes equal to or 1 different.

We can can ensure the number is in the right queue by making a pass through both queues. Add the number to one of the queues, then poll one value from that queue and move it to the other one. You can ensure the queues are the right size either before the previous operation or afterwards by checking the sizes and moving numbers as needed.

When getting the median value there are 2 cases:

1. If the sizes of the queues are equal, return the average of the top values in both queues.
2. If not, then return the top value from the larger queue.