Weekly Programming Challenge #5

Priority Queues and Binary Heaps

I can’t quite believe we’re already up to week #5! I’m excited about this one, but maybe it’s just because I have a soft spot for data types and algorithms. We’ll be implementing a priority queue, using a binary heap.

But first, let’s recap challenge #4!

Week #4 Recap

Last week’s challenge was to implement a program that drew lines onto a canvas of your own creation, using Bresenham’s algorithm (or a variation thereof), and then wrote that canvas to a file in PPM format. Doing this earned you one point. Going further (anti-aliasing, line styles, line thickness, etc.) earned you additional points.

We had five participants last week, not counting myself:

• Martin Moberg got two points for his submission in Clojure, implementing line styles (dashes and dots) on top of the basic requirements: https://github.com/indifferen7/line-drawer
• Steve Desmond also got two points for his C# submission, implementing anti-aliased lines. (He also implemented his own line drawing algorithms, using nothing but maths and geometry!) https://github.com/stevedesmond-ca/WeeklyChallenges/tree/master/04-Lines
• Lasse Ebert’s submission was in Elixir, and he claimed one point: https://github.com/lasseebert/jamis_challenge/tree/master/004_image
• Anders Engström also earned one point for his Clojure submission: https://github.com/metamorph/drawing-lines
• Sri Thaiyar’s Ruby submission got one point as well: https://github.com/sri/weekly-challenges/tree/master/004-draw-lines

My own submission was in Rust, and while I struggled with some areas of that language, I did manage to implement line thickness (using Murphy’s algorithm), and line styles (though not as robustly as I would have liked), and so earned three points: https://github.com/jamis/weekly-challenges/tree/master/004-draw-lines

Great work, everyone! One of my favorite things is seeing how these challenges come together in different programming languages. Thanks to everyone for participating!

Weekly Programming Challenge #5

For this week’s challenge, you must implement a priority queue. This is basically a regular queue, but the elements are each assigned a priority, and elements are removed from the queue in order of priority, regardless of the order in which they were added.

These have many practical applications. Compression algorithms are fond of these queues, since the process of generating a Huffman code requires you to fetch lowest frequency (priority) items. Dijkstra’s algorithm, for finding optimal paths through graphs and networks, can also be implemented with a priority queue.

Such a queue is easy enough to implement on top of a simple list. Each time you fetch the next element, you search the list for the item with the highest (or lowest) priority, and return it. This has terrible performance, though. It’s O(n) for every fetch, which has the potential to be very slow on large lists.

A better implementation uses a heap, basically a tree that keeps its elements sorted. For this challenge you need to implement your priority queue with a binary heap. Wikipedia has an excellent description of binary heaps and their related algorithms, so I’ll refer you there for the details — https://en.wikipedia.org/wiki/Binary_heap.

Normal Mode

The basic, normal submission must implement the following:

1. Implement a binary heap with both insert and extract operations. The insert operation adds an element to the heap, and extract returns the next element from the heap.
2. The heap may be either a min-heap (sorting elements so that the lowest value is first), or a max-heap (sorting so the highest value is first).
3. In order to implement a priority queue, your insert operation must accept a data item (like a number, or a string — you may choose the data type yourself), and an integer priority. The extract operation must remove and return the data item associated with the lowest priority (min-heap) or greatest priority (max-heap).

Hard Mode

For hard mode, let’s use the point system again. You get one point for normal mode, and one additional point for each of the following that you implement:

1. Make your queue configurable, allowing a custom sorting function to be specified in some way. This function will determine which element the extract operation returns. (Note that the sorting function only needs to consider to the priority numbers.)
2. Allow arbitrary data types to be stored in your queue. The queue does not need to heterogeneous, but you ought to be able to instantiate a queue that orders strings, and one that orders numbers, and so forth.
3. Allow the priority of an existing element to be adjusted.
4. Use your queue to implement a Huffman coder! Accept as input some text, and emit a Huffman coding of that text. (TWO POINTS for this one.)
5. Use your queue to implement Dijkstra’s algorithm! Accept as input some description of a network (nodes and edges, where the edges may be weighted), and emit a shortest path through that network. (TWO POINTS for this one.)

As always, “surprise me” mode is always an option, too. Do something creative, clever, or surprising, and earn some extra street cred. It doesn’t have to be fiendishly difficult. All it needs is to show that you thought about the challenge in an unexpected way. Outside the box, so to speak.

This challenge will run until Saturday, September 3rd, at 12:00pm MDT (18:00 UTC).

Submissions are now closed for this challenge, but feel free to try your hand at it anyway! If you’re following along, the next week’s challenge is “Let’s make some noise”. See you there!