Mirror of forum.nim-lang.org

1244 :: Binary heap / priority queue implementation

• bluenote (orginal) [2015-05-19T17:32:56+02:00] view original

  For one of my algorithms I needed a priority queue, and I couldn't find one in the standard library. I have written a very simple binary heap implementation, maybe it is useful for others:

  https://github.com/bluenote10/nim-heap

  The only functionality that goes beyond the mere basics is an optimized implementation of push+pop and pop+push (fairly frequent use case in my domain and I always cringe when doing both steps explicitly).

  As a reference: For a more fancy implementation (paired heap), I have also found something interesting in the IRC logs:

  http://irclogs.nim-lang.org/29-04-2014.html

  https://bitbucket.org/mrzv/heap.nim/overview

  Doesn't have the combined push/pop functionality though.

---

• dom96 (orginal) [2015-05-19T18:12:54+02:00] view original

  Please create a Nimble package out of it and add it to the packages repo.

---

• mora (orginal) [2015-05-20T09:12:59+02:00] view original

  I've checked your code, it was very easy to read, thanks. You had a comment why not have byte instead of int as a return type for cmp. I believe that int is faster for the processor to work with (for byte it uses paddings, shifts), and you couldn't save memory because everything is aligned to 4/8 bytes. If you have more than one return values, then I guess that returning (byte,byte) has a lower memory footprint than (int,int).

---