# heaps

## Priority Queues

Introduction You have N distinct jobs to process, and you are given the responsibility to schedule them on the only available job processor. New jobs keeps on getting added into the set of available jobs. Not all the jobs are to be executed as they come. There might be few which needs to be executed immediately and few can be postponed for some time. You have an efficiently algorithm to decide the priority of an incoming job. The task at hand is as follows: To schedule available jobs based on the priority assigned to them. Add new jobs to the set after assigning a priority to it. ...

## Median of a Stream of Integers

[nextpage title="Problem Statement"] Here is a very interesting problem which has been asked in many interviews and coding competitions. The problem statement goes as follows: Given a never ending stream of number, at any point in time, find the median of all the numbers received till that point. This means, we need to recalculate the new median whenever there is a number available in the input stream. This problems seems to be a very practical one, imagine a lot of sensors in manufacturing plants are pushing data about temperature, pressure and other physical parameters. It is very importa...

## Operations on a Heap

Introduction In this post, we will try to put together all the leanings from the previous posts and define the basic operations on a heap. Also, we will try and derive the running time of each such operation and write code for the same. Also, we will discuss an interesting problem statement which can be easily solved using the heap property. Basic Operations on Heap The heap can support the following basic operations as any other data structure IncreaseKey - Changes the key value of a given node to a new value. It is assumed that the new value is at least as big as the current value....