Back to course

Heaps and Priority Queues

Implement a heap, or a circular buffer, is one of the most common requests in trading-firm developer interviews, and the heap is the one that separates people, because the textbook version is twenty lines and the version an interviewer actually wants has a piece the textbook usually leaves out.

A heap is an array with an arithmetic rule

A binary heap is a complete binary tree, and a complete binary tree can be stored in a flat array with no pointers at all. For a node at index ii (zero-based):

parent(i)=⌊i−12⌋,left(i)=2i+1,right(i)=2i+2\text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor, \qquad \text{left}(i) = 2i + 1, \qquad \text{right}(i) = 2i + 2

That is the whole structure. The heap property is that every parent compares no greater than its children, for a min-heap, which makes the smallest element index 0 and costs nothing to maintain beyond two operations.

The rest of this lesson is for subscribers

Unlock every lesson in Programming for Quantitative Developers, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Continue
NextCaches: LRU, LFU, and What They Are Really Testing

Keep reading Programming for Quantitative Developers

25 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them