RubyGems.org

This is a fibonacci-heap priority-queue implementation. That means insert: O(1) decrease_priority: Amortized O(1) delete_min: Amortized O(log n) This project is different from K. Kodamas PQueue in that it allows a decrease key operation. That makes PriorityQueue usable for algorithms like dijkstras shortest path algorithm, while PQueue is more suitable for Heapsort and the like.

installgem install PriorityQueue
Authors

Brian Schroeder

84,573 total downloads 81,988 for this version
Owners

50f981ff37f4abfc1d3a420aae4f6513

Gemfile
gem 'PriorityQueue', '~> 0.1.2'
Versions
  1. 0.1.2 October 29, 2005 (58 KB)
  2. 0.1.1 October 25, 2005 (42 KB)
  3. 0.1.0 October 25, 2005 (60 KB)