Script 'mail_helper' called by obssrc
Hello community,
here is the log from the commit of package rubygem-pairing_heap for
openSUSE:Factory checked in at 2022-10-12 18:24:51
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/rubygem-pairing_heap (Old)
and /work/SRC/openSUSE:Factory/.rubygem-pairing_heap.new.2275 (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "rubygem-pairing_heap"
Wed Oct 12 18:24:51 2022 rev:2 rq:1010028 version:1.0.0
Changes:
--------
---
/work/SRC/openSUSE:Factory/rubygem-pairing_heap/rubygem-pairing_heap.changes
2022-09-26 18:48:11.400052690 +0200
+++
/work/SRC/openSUSE:Factory/.rubygem-pairing_heap.new.2275/rubygem-pairing_heap.changes
2022-10-12 18:26:31.393931782 +0200
@@ -1,0 +2,6 @@
+Mon Oct 10 13:13:36 UTC 2022 - Stephan Kulow <[email protected]>
+
+updated to version 1.0.0
+ no changelog found
+
+-------------------------------------------------------------------
Old:
----
pairing_heap-0.3.0.gem
New:
----
pairing_heap-1.0.0.gem
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ rubygem-pairing_heap.spec ++++++
--- /var/tmp/diff_new_pack.7UkkPa/_old 2022-10-12 18:26:31.837932760 +0200
+++ /var/tmp/diff_new_pack.7UkkPa/_new 2022-10-12 18:26:31.841932769 +0200
@@ -16,26 +16,28 @@
#
-%define mod_name pairing_heap
-%define mod_full_name %{mod_name}-%{version}
#
# This file was generated with a gem2rpm.yml and not just plain gem2rpm.
# All sections marked as MANUAL, license headers, summaries and descriptions
# can be maintained in that file. Please consult this file before editing any
# of those fields
#
+
Name: rubygem-pairing_heap
-Version: 0.3.0
+Version: 1.0.0
Release: 0
-Summary: Performant priority queue in pure ruby with support for
changing
-License: MIT
-Group: Development/Languages/Ruby
-URL: https://github.com/mhib/pairing_heap
-Source: https://rubygems.org/gems/%{mod_full_name}.gem
-Source1: gem2rpm.yml
+%define mod_name pairing_heap
+%define mod_full_name %{mod_name}-%{version}
+BuildRoot: %{_tmppath}/%{name}-%{version}-build
BuildRequires: %{ruby >= 2.3.0}
BuildRequires: %{rubygem gem2rpm}
BuildRequires: ruby-macros >= 5
+URL: https://github.com/mhib/pairing_heap
+Source: https://rubygems.org/gems/%{mod_full_name}.gem
+Source1: gem2rpm.yml
+Summary: Performant priority queue in pure ruby with support for
changing
+License: MIT
+Group: Development/Languages/Ruby
%description
Performant priority queue in pure ruby with support for changing priority
@@ -54,7 +56,6 @@
find %{buildroot}/%{_libdir}/ruby/gems/ \( -name '.rubocop.yml' -o -name
'.github' -o -name '.gitignore' \) | xargs rm -rf
# /MANUAL
-
%gem_packages
%changelog
++++++ pairing_heap-0.3.0.gem -> pairing_heap-1.0.0.gem ++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/.github/workflows/main.yml
new/.github/workflows/main.yml
--- old/.github/workflows/main.yml 2022-02-08 20:45:24.000000000 +0100
+++ new/.github/workflows/main.yml 2022-09-04 21:41:24.000000000 +0200
@@ -1,18 +1,21 @@
name: Ruby
on: [push,pull_request]
-
jobs:
build:
- runs-on: ubuntu-latest
+ strategy:
+ fail-fast: false
+ matrix:
+ os: [ubuntu-latest, macos-latest]
+ # Due to https://github.com/actions/runner/issues/849, we have to use
quotes for '3.0'
+ ruby: ['2.3', '2.7', '3.0', '3.1', head, jruby, jruby-head,
truffleruby, truffleruby-head]
+ runs-on: ${{ matrix.os }}
steps:
- - uses: actions/checkout@v2
- - name: Set up Ruby
- uses: ruby/setup-ruby@v1
+ - uses: actions/checkout@v3
+ - uses: ruby/setup-ruby@v1
with:
- ruby-version: 3.0.0
- - name: Run the default task
- run: |
+ ruby-version: ${{ matrix.ruby }}
+ - run: |
gem install bundler -v 2.2.3
bundle install
bundle exec rake
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/README.md new/README.md
--- old/README.md 2022-02-08 20:45:24.000000000 +0100
+++ new/README.md 2022-09-04 21:41:24.000000000 +0200
@@ -2,7 +2,9 @@
PairingHeap is a pure Ruby priority queue implementation using a pairing heap
as the underlying data structure. While a pairing heap is asymptotically less
efficient than the Fibonacci heap, it is usually faster in practice. This makes
it a popular choice for Prim's MST or Dijkstra's algorithm implementations.
-Also implementation without priority change support is
provided(`SimplePairingHeap`), while the asymptotical complexity of the methods
stay the same, bookkeeping of elements is not needed making the constant
smaller.
+PairingHeap is currently being used as the priority queue data structure in
[RGL](https://github.com/monora/rgl/).
+
+Also implementation without priority change support is
provided(`SimplePairingHeap`), while the asymptotical complexity of the methods
stay the same, bookkeeping of elements is not needed making, the constant
smaller.
## Installation
@@ -104,7 +106,7 @@
## Benchmarks
I picked the three fastest pure Ruby priority queue implementations I was
aware of for the comparison:
-*
[lazy_priority_queue](https://github.com/matiasbattocchia/lazy_priority_queue)
that uses a lazy binomial heap. This is probably the most popular option, used
for example in [RGL](https://github.com/monora/rgl/)
+*
[lazy_priority_queue](https://github.com/matiasbattocchia/lazy_priority_queue)
that uses a lazy binomial heap. This is probably the most popular option. It
was used in [RGL](https://github.com/monora/rgl/) until PairingHeap replaced it.
* Pure Ruby implementation of Fibonacci Heap from
[priority-queue](https://github.com/supertinou/priority-queue) ([link to
source](https://github.com/supertinou/priority-queue/blob/master/lib/priority_queue/ruby_priority_queue.rb))
* [rb_heap](https://github.com/florian/rb_heap) that uses a binary heap. Note
however that this implementation does not support change_priority operation.
@@ -114,7 +116,7 @@
> A stress test of 1,000,000 operations: starting with 1,000 pushes/0 pops,
> following 999 pushes/1 pop, and so on till 0 pushes/1000 pops.
<table>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16)
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a)
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -124,36 +126,36 @@
</tr>
<tr>
<td>pairing_heap (SimplePairingHeap)</td>
- <td>18</td>
- <td>60.232046</td>
- <td>0.299</td>
+ <td>23</td>
+ <td>62.014773</td>
+ <td>0.371</td>
</tr>
<tr>
<td>pairing_heap (PairingHeap)</td>
- <td>15</td>
- <td>63.978031</td>
- <td>0.234(1.27x slower)</td>
+ <td>16</td>
+ <td>63.135240</td>
+ <td>0.253(1.46x slower)</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>9</td>
- <td>60.031283</td>
- <td>0.150(1.99x slower)</td>
+ <td>rb_heap</td>
+ <td>14</td>
+ <td>61.123304</td>
+ <td>0.229(1.62x slower)</td>
</tr>
<tr>
- <td>rb_heap</td>
- <td>9</td>
- <td>60.497355</td>
- <td>0.149(2.01x slower)</td>
+ <td>lazy_priority_queue</td>
+ <td>10</td>
+ <td>66.208647</td>
+ <td>0.151(2.46x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
<td>8</td>
- <td>66.866055</td>
- <td>0.120(2.50x slower)</td>
+ <td>66.353147</td>
+ <td>0.121(3.08x slower)</td>
</tr>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -163,36 +165,36 @@
</tr>
<tr>
<td>pairing_heap (SimplePairingHeap)</td>
- <td>22</td>
- <td>62.866807</td>
- <td>0.350</td>
+ <td>25</td>
+ <td>60.423579</td>
+ <td>0.414</td>
+ </tr>
+ <tr>
+ <td>rb_heap</td>
+ <td>19</td>
+ <td>60.869907</td>
+ <td>0.312(1.33x slower)</td>
</tr>
<tr>
<td>pairing_heap (PairingHeap)</td>
- <td>16</td>
- <td>61.358679</td>
- <td>0.261(1.34x slower)</td>
+ <td>17</td>
+ <td>61.389127</td>
+ <td>0.277(1.49x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
<td>14</td>
- <td>64.394112</td>
- <td>0.217(1.61x slower)</td>
- </tr>
- <tr>
- <td>rb_heap</td>
- <td>12</td>
- <td>60.975479</td>
- <td>0.197(1.78x slower)</td>
+ <td>64.417807</td>
+ <td>0.217(1.90x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
<td>11</td>
- <td>65.568648</td>
- <td>0.168(2.09x slower)</td>
+ <td>63.151856</td>
+ <td>0.174(2.38x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64]</th>
+ <th colspan="4">jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit
Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -202,36 +204,36 @@
</tr>
<tr>
<td>pairing_heap (SimplePairingHeap)</td>
- <td>21</td>
- <td>60.357577s</td>
- <td>0.348</td>
+ <td>47</td>
+ <td>60.391633</td>
+ <td>0.778</td>
</tr>
<tr>
- <td>pairing_heap (PairingHeap)</td>
- <td>15</td>
- <td>60.417252</td>
- <td>0.248(1.40x slower)</td>
+ <td>rb_heap</td>
+ <td>34</td>
+ <td>60.878639</td>
+ <td>0.559(1.39x slower)</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>14</td>
- <td>61.022450</td>
- <td>0.229(1.52x slower)</td>
+ <td>pairing_heap (PairingHeap)</td>
+ <td>32</td>
+ <td>61.211985</td>
+ <td>0.523(1.49x slower)</td>
</tr>
<tr>
- <td>rb_heap</td>
- <td>13</td>
- <td>63.661862</td>
- <td>0.204(1.70x slower)</td>
+ <td>Fibonacci</td>
+ <td>23</td>
+ <td>60.297670</td>
+ <td>0.382(2.04x slower)</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>8</td>
- <td>62.643449</td>
- <td>0.128(2.72x slower)</td>
+ <td>lazy_priority_queue</td>
+ <td>23</td>
+ <td>61.973538</td>
+ <td>0.371(2.10x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64]</th>
+ <th colspan="4">truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM
[x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -241,33 +243,33 @@
</tr>
<tr>
<td>pairing_heap (SimplePairingHeap)</td>
- <td>43</td>
- <td>60.472129</td>
- <td>0.711</td>
+ <td>206</td>
+ <td>60.191686</td>
+ <td>3.433</td>
</tr>
<tr>
- <td>pairing_heap (PairingHeap)</td>
- <td>30</td>
- <td>60.359748</td>
- <td>0.497(1.43x slower)</td>
+ <td>rb_heap</td>
+ <td>97</td>
+ <td>60.134011</td>
+ <td>1.614(1.93x slower)</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>25</td>
- <td>62.084250</td>
- <td>0.403(1.77x slower)</td>
+ <td>pairing_heap (PairingHeap)</td>
+ <td>85</td>
+ <td>60.193608s</td>
+ <td>1.434(2.40x slower)</td>
</tr>
<tr>
- <td>rb_heap</td>
- <td>23</td>
- <td>62.419893</td>
- <td>0.369(1.93x slower)</td>
+ <td>lazy_priority_queue</td>
+ <td>19</td>
+ <td>63.212429</td>
+ <td>0.301(11.45x slower)</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>22</td>
- <td>60.947299</td>
- <td>0.361(1.97x slower)</td>
+ <td>Fibonacci</td>
+ <td>2</td>
+ <td>83.508571</td>
+ <td>0.024(143.70x slower)</td>
</tr>
</table>
@@ -275,7 +277,7 @@
A stress test of 1,501,500 operations: starting with 1,000 pushes/1000
change_priorities/0 pops, following 999 pushes/999 change_priorities/1 pop, and
so on till 0 pushes/0 change_priorities/1000 pops.
<table>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16)
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a)
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -285,24 +287,24 @@
</tr>
<tr>
<td>pairing_heap</td>
- <td>14</td>
- <td>63.536300</td>
- <td>0.220</td>
+ <td>15</td>
+ <td>62.946988</td>
+ <td>0.238</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
<td>9</td>
- <td>63.319474s</td>
- <td>0.142(1.55x slower)</td>
+ <td>61.876691</td>
+ <td>0.145(1.64x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
<td>8</td>
- <td>67.385714</td>
- <td>0.119(1.86x slower)</td>
+ <td>67.809982</td>
+ <td>0.118(2.02x slower)</td>
</tr>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -312,24 +314,24 @@
</tr>
<tr>
<td>pairing_heap</td>
- <td>15</td>
- <td>62.243080</td>
- <td>0.241</td>
+ <td>16</td>
+ <td>62.576693</td>
+ <td>0.256</td>
</tr>
<tr>
<td>Fibonacci</td>
<td>13</td>
- <td>63.030390</td>
- <td>0.206(1.17x slower)</td>
+ <td>63.164614</td>
+ <td>0.206(1.24x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
<td>10</td>
- <td>64.865853</td>
- <td>0.154(1.56x slower)</td>
+ <td>63.172995s</td>
+ <td>0.158(1.62x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64]</th>
+ <th colspan="4">jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit
Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -339,24 +341,24 @@
</tr>
<tr>
<td>pairing_heap</td>
- <td>15</td>
- <td>61.540851</td>
- <td>0.244</td>
+ <td>28</td>
+ <td>60.280368</td>
+ <td>0.465</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>14</td>
- <td>61.471507</td>
- <td>0.228(1.07x slower)</td>
+ <td>Fibonacci</td>
+ <td>22</td>
+ <td>61.405561</td>
+ <td>0.465(1.30x slower)</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>9</td>
- <td>67.393730</td>
- <td>0.134(1.83x slower)</td>
+ <td>lazy_priority_queue</td>
+ <td>20</td>
+ <td>60.397535</td>
+ <td>0.331(1.40x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64]</th>
+ <th colspan="4">truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM
[x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -366,48 +368,58 @@
</tr>
<tr>
<td>pairing_heap</td>
- <td>27</td>
- <td>61.322001</td>
- <td>0.440</td>
+ <td>70</td>
+ <td>60.663184</td>
+ <td>1.160</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>21</td>
- <td>60.334636</td>
- <td>0.349(1.26x slower)</td>
+ <td>lazy_priority_queue</td>
+ <td>23</td>
+ <td>60.474587</td>
+ <td>0.382(3.04x slower)</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>20</td>
- <td>61.471507</td>
- <td>0.327(1.35x slower)</td>
+ <td>Fibonacci</td>
+ <td>2</td>
+ <td>74.873854</td>
+ <td>0.027(43.44x slower)</td>
</tr>
</table>
-### Stress test with changing priority(N = 10) [source
code](./test/performance_with_change_priority.rb)
-A stress test of 165 operations: starting with 10 pushes/10
change_priorities/0 pops, following 9 pushes/9 change_priorities/1 pop, and so
on till 0 pushes/0 change_priorities/10 pops.
+### Stress test with changing priority or push/pop(test ignored in summary)
[source code](./test/performance_pop_versus_change_priority.rb)
+Start with 500 pushes, then:
+ * If queue supports changing priority 500 change_priority calls, then 500
pops
+ * If does not support changing priority 500 push calls, then 1000 pops
<table>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16)
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a)
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
<th>Iterations per second</th>
</tr>
<tr>
- <td>pairing_heap</td>
- <td>5914.3</td>
+ <td>pairing_heap (PairingHeap)</td>
+ <td>436.4</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>4293.5(1.38x slower)</td>
+ <td>380.2(1.94x slower)</td>
+ </tr>
+ <tr>
+ <td>pairing_heap (SimplePairingHeap)</td>
+ <td>339.9.02(2.17x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>3755.2(1.57x slower)</td>
+ <td>313.9(2.35x slower)</td>
+ </tr>
+ <tr>
+ <td>rb_heap</td>
+ <td>194.7(3.78 slower)</td>
</tr>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -415,60 +427,84 @@
</tr>
<tr>
<td>pairing_heap</td>
- <td>7082.7</td>
+ <td>854.6</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>6687.1(1.06x slower)</td>
+ <td>651.3(1.31x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>5006.4(1.41x slower)</td>
+ <td>453.6(1.88x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64]</th>
+ <td>pairing_heap(SimplePairingHeap)</td>
+ <td>390.9(2.19x slower)</td>
+ </tr>
+ <tr>
+ <td>rb_heap</td>
+ <td>268.8(3.18x slower)</td>
+ </tr>
+ <tr>
+ <th colspan="4">jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit
Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
<th>Iterations per second</th>
</tr>
<tr>
- <td>pairing_heap</td>
- <td>6861.6</td>
+ <td>pairing_heap(PairingHeap)</td>
+ <td>1591</td>
+ </tr>
+ <tr>
+ <td>Fibonacci</td>
+ <td>1092(1.46x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>6446.4(1.06x slower)</td>
+ <td>986(1.61x slower)</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>4365.4(1.57x slower)</td>
+ <td>pairing_heap(SimplePairingHeap)</td>
+ <td>562(2.37x slower)</td>
+ </tr>
+ <tr>
+ <td>rb_heap</td>
+ <td>623(2.55x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64]</th>
+ <th colspan="4">truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM
[x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
<th>Iterations per second</th>
</tr>
<tr>
- <td>pairing_heap</td>
- <td>14032</td>
+ <td>pairing_heap(PairingHeap)</td>
+ <td>7404</td>
+ </tr>
+ <tr>
+ <td>pairing_heap(SimplePairingHeap)</td>
+ <td>5104(1.45x slower)</td>
+ </tr>
+ <tr>
+ <td>rb_heap</td>
+ <td>1575(4.70x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>12841(1.09x slower)</td>
+ <td>1258(5.88x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>10404(1.35x slower)</td>
+ <td>1004(7.38x slower)</td>
</tr>
</table>
### Dijkstra's algorithm with RGL [source code](./test/performance_rgl.rb)
<table>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16)
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a)
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -479,23 +515,23 @@
<tr>
<td>pairing_heap</td>
<td>9</td>
- <td>64.505899</td>
- <td>0.140</td>
+ <td>61.469343</td>
+ <td>0.116</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
<td>8</td>
- <td>63.970577</td>
- <td>0.125(1.12x slower)</td>
+ <td>64.312672</td>
+ <td>0.125(1.18x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
<td>7</td>
- <td>62.573724</td>
- <td>0.112(1.25x slower)</td>
+ <td>60.555716</td>
+ <td>0.116(1.27x slower)</td>
</tr>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -505,24 +541,24 @@
</tr>
<tr>
<td>pairing_heap</td>
- <td>9</td>
- <td>63.567801</td>
- <td>0.142</td>
+ <td>10</td>
+ <td>65.160945s</td>
+ <td>0.154</td>
</tr>
<tr>
<td>Fibonacci</td>
<td>9</td>
- <td>64.575079</td>
- <td>0.140(1.02x slower)</td>
+ <td>61.950587</td>
+ <td>0.145(1.06x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>8</td>
- <td>60.123700</td>
- <td>0.133(1.06x slower)</td>
+ <td>9</td>
+ <td>66.592123</td>
+ <td>0.135(1.14x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64]</th>
+ <th colspan="4">jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit
Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -531,25 +567,25 @@
<th>Iterations per second</th>
</tr>
<tr>
- <td>pairing_heap</td>
- <td>14</td>
- <td>64.124373</td>
- <td>0.218</td>
+ <td>lazy_priority_queue</td>
+ <td>20</td>
+ <td>61.149944</td>
+ <td>0.328</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>13</td>
- <td>61.147807</td>
- <td>0.213(1.03x slower)</td>
+ <td>pairing_heap</td>
+ <td>20</td>
+ <td>61.210225s</td>
+ <td>0.328</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>10</td>
- <td>64.250067</td>
- <td>0.156(1.40x slower)</td>
+ <td>18</td>
+ <td>62.330882</td>
+ <td>0.292(1.12x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64]</th>
+ <th colspan="4">truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM
[x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -559,21 +595,21 @@
</tr>
<tr>
<td>pairing_heap</td>
- <td>22</td>
- <td>61.450341</td>
- <td>0.361</td>
+ <td>59</td>
+ <td>60.053843</td>
+ <td>0.991</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>18</td>
- <td>61.618204</td>
- <td>0.296(1.22x slower)</td>
+ <td>lazy_priority_queue</td>
+ <td>34</td>
+ <td>60.586461</td>
+ <td>0.563(1.76x slower)</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>17</td>
- <td>60.156184</td>
- <td>0.283(1.27x slower)</td>
+ <td>Fibonacci</td>
+ <td>31</td>
+ <td>60.633711</td>
+ <td>0.520(1.90x slower)</td>
</tr>
</table>
@@ -581,7 +617,7 @@
Heaps that support change_priority operation use it. Heaps that do not support
it use dijkstra implementation that do not rely on change_priority instead and
do additional pops and pushes instead(see Dijkstra-NoDec from [Priority Queues
and Dijkstra???s
Algorithm](https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf)).
<table>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16)
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a)
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -591,36 +627,36 @@
</tr>
<tr>
<td>pairing_heap (SimplePairingHeap)</td>
- <td>25</td>
- <td>61.386477</td>
- <td>0.407</td>
+ <td>28</td>
+ <td>62.100299</td>
+ <td>0.451</td>
</tr>
<tr>
<td>pairing_heap (PairingHeap)</td>
- <td>22</td>
- <td>62.044470</td>
- <td>0.355(1.15x slower)</td>
+ <td>23</td>
+ <td>60.633153</td>
+ <td>0.380(1.19x slower)</td>
</tr>
<tr>
<td>rb_heap</td>
- <td>13</td>
- <td>60.717112</td>
- <td>0.214(1.90x slower)</td>
+ <td>14</td>
+ <td>62.019763</td>
+ <td>0.226(2.00x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>10</td>
- <td>61.730614</td>
- <td>0.162(2.51x slower)</td>
+ <td>11</td>
+ <td>63.105064s</td>
+ <td>0.174(2.58x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
<td>10</td>
- <td>65.899982</td>
- <td>0.152(2.68x slower)</td>
+ <td>64.407187</td>
+ <td>0.155(2.90x slower)</td>
</tr>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -630,36 +666,36 @@
</tr>
<tr>
<td>pairing_heap (SimplePairingHeap)</td>
- <td>29</td>
- <td>61.656995</td>
- <td>0.471</td>
+ <td>32</td>
+ <td>61.289321</td>
+ <td>0.522</td>
</tr>
<tr>
<td>pairing_heap (PairingHeap)</td>
- <td>24</td>
- <td>61.813482</td>
- <td>0.389(1.21x slower)</td>
+ <td>26</td>
+ <td>60.657625</td>
+ <td>0.429(1.22x slower)</td>
</tr>
<tr>
<td>rb_heap</td>
<td>19</td>
- <td>62.191040</td>
- <td>0.306(1.54x slower)</td>
+ <td>60.710888s</td>
+ <td>0.313(1.67x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>18</td>
- <td>60.062072</td>
- <td>0.300(1.57x slower)</td>
+ <td>19</td>
+ <td>61.471203</td>
+ <td>0.310(1.69x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
<td>12</td>
- <td>60.860292</td>
- <td>0.197(2.38x slower)</td>
+ <td>60.125779</td>
+ <td>0.200(2.61x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64]</th>
+ <th colspan="4">jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit
Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -669,36 +705,36 @@
</tr>
<tr>
<td>pairing_heap (SimplePairingHeap)</td>
- <td>24</td>
- <td>61.972936</td>
- <td>0.387</td>
+ <td>46</td>
+ <td>61.226924</td>
+ <td>0.753</td>
</tr>
<tr>
- <td>pairing_heap (PairingHeap)</td>
- <td>20</td>
- <td>62.178839</td>
- <td>0.322(1.20x slower)</td>
+ <td>rb_heap</td>
+ <td>38</td>
+ <td>60.563995</td>
+ <td>0.628(1.20x slower)</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>14</td>
- <td>61.540058s</td>
- <td>0.228(1.70x slower)</td>
+ <td>pairing_heap (PairingHeap)</td>
+ <td>37</td>
+ <td>60.928350</td>
+ <td>0.608(1.24x slower)</td>
</tr>
<tr>
- <td>rb_heap</td>
- <td>14</td>
- <td>62.125831</td>
- <td>0.225(1.72x slower)</td>
+ <td>Fibonacci</td>
+ <td>28</td>
+ <td>61.136970</td>
+ <td>0.461(1.63x slower)</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>10</td>
- <td>62.319669</td>
- <td>0.155(2.41x slower)</td>
+ <td>lazy_priority_queue</td>
+ <td>22</td>
+ <td>62.214796</td>
+ <td>0.354(2.13x slower)</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64]</th>
+ <th colspan="4">truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM
[x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -708,33 +744,33 @@
</tr>
<tr>
<td>pairing_heap (SimplePairingHeap)</td>
- <td>47</td>
- <td>61.192519</td>
- <td>0.770</td>
+ <td>176</td>
+ <td>60.029817</td>
+ <td>3.006</td>
</tr>
<tr>
- <td>rb_heap</td>
- <td>39</td>
- <td>61.028398</td>
- <td>0.639(1.20x slower)</td>
+ <td>pairing_heap (PairingHeap)</td>
+ <td>124</td>
+ <td>60.366607</td>
+ <td>2.078(1.45x slower)</td>
</tr>
<tr>
- <td>pairing_heap (PairingHeap)</td>
- <td>36</td>
- <td>60.035760</td>
- <td>0.601(1.28x slower)</td>
+ <td>rb_heap</td>
+ <td>95</td>
+ <td>60.021043</td>
+ <td>1.585(1.90x slower)</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>28</td>
- <td>61.599202</td>
- <td>0.456(1.69x slower)</td>
+ <td>38</td>
+ <td>60.020976</td>
+ <td>0.636(4.72x slower)</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>22</td>
- <td>60.540367</td>
- <td>0.364(2.12x slower)</td>
+ <td>27</td>
+ <td>61.349925</td>
+ <td>0.445(6.75x slower)</td>
</tr>
</table>
@@ -742,7 +778,7 @@
#### Change priority required
<table>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16)
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a)
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -754,14 +790,14 @@
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>1.523x slower</td>
+ <td>1.688x slower</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>1.751x slower</td>
+ <td>1.987x slower</td>
</tr>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -773,14 +809,14 @@
</tr>
<tr>
<td>Fibonacci</td>
- <td>1.146x slower</td>
+ <td>1.256x slower</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>1.482x slower</td>
+ <td>1.648x slower</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64]</th>
+ <th colspan="4">jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit
Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -791,16 +827,15 @@
<td>1</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>1.153x slower</td>
-
+ <td>Fibonacci</td>
+ <td>1.327x slower</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>1.793x slower</td>
+ <td>lazy_priority_queue</td>
+ <td>1.383x slower</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64]</th>
+ <th colspan="4">truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM
[x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -811,19 +846,19 @@
<td>1</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>1.222x slower</td>
+ <td>lazy_priority_queue</td>
+ <td>3.878x slower</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>1.394x slower</td>
+ <td>Fibonacci</td>
+ <td>9.889x slower</td>
</tr>
</table>
#### Change priority not required
<table>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16)
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a)
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -835,22 +870,22 @@
</tr>
<tr>
<td>pairing_heap (PairingHeap)</td>
- <td>1.209x slower</td>
+ <td>1.318x slower</td>
</tr>
<tr>
<td>rb_heap</td>
- <td>1.954x slower</td>
+ <td>1.8x slower</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>2.235x slower</td>
+ <td>2.519x slower</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>2.588x slower</td>
+ <td>2.989x slower</td>
</tr>
<tr>
- <th colspan="4">ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT
[x86_64-darwin21]</th>
+ <th colspan="4">ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT
[x86_64-darwin21]</th>
</tr>
<tr>
<th>Library</th>
@@ -862,22 +897,22 @@
</tr>
<tr>
<td>pairing_heap (PairingHeap)</td>
- <td>1.273x slower</td>
+ <td>1.348x slower</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>1.590x slower</td>
+ <td>rb_heap</td>
+ <td>1.490x slower</td>
</tr>
<tr>
- <td>rb_heap</td>
- <td>1.666x slower</td>
+ <td>Fibonacci</td>
+ <td>1.792x slower</td>
</tr>
<tr>
<td>lazy_priority_queue</td>
- <td>2.230x slower</td>
+ <td>2.492x slower</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64]</th>
+ <th colspan="4">jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit
Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -888,23 +923,23 @@
<td>1</td>
</tr>
<tr>
- <td>pairing_heap (PairingHeap)</td>
- <td>1.296x slower</td>
+ <td>rb_heap</td>
+ <td>1.292x slower</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>1.607x slower</td>
+ <td>pairing_heap (PairingHeap)</td>
+ <td>1.359x slower</td>
</tr>
<tr>
- <td>rb_heap</td>
- <td>1.710x slower</td>
+ <td>lazy_priority_queue</td>
+ <td>2.115x slower</td>
</tr>
<tr>
<td>Fibonacci</td>
- <td>2.452x slower</td>
+ <td>1.824x slower</td>
</tr>
<tr>
- <th colspan="4">jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit
Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64]</th>
+ <th colspan="4">truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM
[x86_64-darwin]</th>
</tr>
<tr>
<th>Library</th>
@@ -916,19 +951,19 @@
</tr>
<tr>
<td>pairing_heap (PairingHeap)</td>
- <td>1.353x slower</td>
+ <td>1.865x slower</td>
</tr>
<tr>
<td>rb_heap</td>
- <td>1.522x slower</td>
+ <td>1.915x slower</td>
</tr>
<tr>
- <td>Fibonacci</td>
- <td>1.730x slower</td>
+ <td>lazy_priority_queue</td>
+ <td>8.791x slower</td>
</tr>
<tr>
- <td>lazy_priority_queue</td>
- <td>2.044x slower</td>
+ <td>Fibonacci</td>
+ <td>26.044x slower</td>
</tr>
</table>
Binary files old/checksums.yaml.gz and new/checksums.yaml.gz differ
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/lib/pairing_heap/version.rb
new/lib/pairing_heap/version.rb
--- old/lib/pairing_heap/version.rb 2022-02-08 20:45:24.000000000 +0100
+++ new/lib/pairing_heap/version.rb 2022-09-04 21:41:24.000000000 +0200
@@ -1,5 +1,5 @@
# frozen_string_literal: true
module PairingHeap
- VERSION = "0.3.0"
+ VERSION = "1.0.0"
end
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/lib/pairing_heap.rb new/lib/pairing_heap.rb
--- old/lib/pairing_heap.rb 2022-02-08 20:45:24.000000000 +0100
+++ new/lib/pairing_heap.rb 2022-09-04 21:41:24.000000000 +0200
@@ -8,18 +8,21 @@
return heaps if heaps.next_sibling.nil?
# [H1, H2, H3, H4, H5, H6, H7] => [H1H2, H3H4, H5H6, H7]
- stack = []
- current = heaps
- while current
- prev = current
- current = current.next_sibling
- unless current
- stack << prev
+ pairs = nil
+ left = heaps
+ while left
+ right = left.next_sibling
+ unless right
+ left.next_sibling = pairs
+ pairs = left
break
end
- next_val = current.next_sibling
- stack << meld(prev, current)
- current = next_val
+ next_val = right.next_sibling
+ right = meld(left, right)
+ right.next_sibling = pairs
+ pairs = right
+
+ left = next_val
end
# [H1H2, H3H4, H5H6, H7]
@@ -27,13 +30,14 @@
# [H1H2, H3H45H67]
# [H1H2H3H45H67]
# return H1H2H3H45H67
- while true
- right = stack.pop
- return right if stack.empty?
-
- left = stack.pop
- stack << meld(left, right)
+ left = pairs
+ right = pairs.next_sibling
+ while right
+ next_val = right.next_sibling
+ left = meld(left, right)
+ right = next_val
end
+ left
end
end
private_constant :MergePairs
@@ -43,13 +47,13 @@
class PairingHeap
class Node
attr_accessor :elem, :priority, :subheaps, :parent, :prev_sibling,
:next_sibling
- def initialize(elem, priority, subheaps, parent, prev_sibling,
next_sibling)
+ def initialize(elem, priority)
@elem = elem
@priority = priority
- @subheaps = subheaps
- @parent = parent
- @prev_sibling = prev_sibling
- @next_sibling = next_sibling
+ @subheaps = nil
+ @parent = nil
+ @prev_sibling = nil
+ @next_sibling = nil
end
def remove_from_parents_list!
@@ -82,12 +86,17 @@
def push(elem, priority)
raise ArgumentError, "Element already in the heap" if @nodes.key?(elem)
- node = Node.new(elem, priority, nil, nil, nil, nil)
+ node = Node.new(elem, priority)
@nodes[elem] = node
- @root = meld(@root, node)
+ if @root
+ @root = meld(@root, node)
+ else
+ @root = node
+ end
self
end
alias enqueue push
+ alias offer push
# Returns the element at the top of the heap
# Time Complexity: O(1)
@@ -96,6 +105,10 @@
end
def peek_priority
+ @root&.priority
+ end
+
+ def peek_with_priority
[@root&.elem, @root&.priority]
end
@@ -118,11 +131,10 @@
end
alias length size
- # Removes element from the top of the heap
+ # Removes element from the top of the heap and returns it
# Time Complexity: O(N)
# Amortized time Complexity: O(log(N))
- # @raise [ArgumEntError] if the heap is empty
- # @return [PairingHeap]
+ # @raise [ArgumentError] if the heap is empty
def pop
raise ArgumentError, "Cannot remove from an empty heap" if @root.nil?
@@ -149,7 +161,7 @@
# Amortized Time Complexity: o(log(N))
# @param elem Element
# @param priority New priority
- # @raise [ArgumentError] if the element heap is not in heap or the new
priority is less prioritary
+ # @raise [ArgumentError] if the element is not in the heap or the new
priority is less prioritary
# @return [PairingHeap]
def change_priority(elem, priority)
node = @nodes[elem]
@@ -171,7 +183,7 @@
# Removes element from the heap
# Time Complexity: O(N)
# Amortized Time Complexity: O(log(N))
- # @raise [ArgumentError] if the element heap is not in heap
+ # @raise [ArgumentError] if the element is not in the heap
# @return [PairingHeap]
def delete(elem)
node = @nodes[elem]
@@ -180,26 +192,37 @@
@nodes.delete(elem)
if node.parent.nil?
@root = merge_pairs(node.subheaps)
+ if @root
+ @root.parent = nil
+ @root.prev_sibling = nil
+ @root.next_sibling = nil
+ end
else
node.remove_from_parents_list!
new_heap = merge_pairs(node.subheaps)
if new_heap
- new_heap.prev_sibling = nil
- new_heap.next_sibling = nil
+ @root = meld(new_heap, @root)
+ @root.parent = nil
+ @root.prev_sibling = nil
+ @root.next_sibling = nil
end
- @root = meld(new_heap, @root)
end
- @root&.parent = nil
self
end
+ # Returns priority of the provided element
+ # Time Complexity: O(1)
+ # @raise [ArgumentError] if the element is not in the heap
+ def get_priority(elem)
+ node = @nodes[elem]
+ raise ArgumentError, "Provided element is not in heap" if node.nil?
+ node.priority
+ end
+
private
include MergePairs
def meld(left, right)
- return right if left.nil?
- return left if right.nil?
-
if @order[left.priority, right.priority]
parent = left
child = right
@@ -219,11 +242,11 @@
class SimplePairingHeap
class Node
attr_accessor :elem, :priority, :subheaps, :next_sibling
- def initialize(elem, priority, subheaps, next_sibling)
+ def initialize(elem, priority)
@elem = elem
@priority = priority
- @subheaps = subheaps
- @next_sibling = next_sibling
+ @subheaps = nil
+ @next_sibling = nil
end
end
private_constant :Node
@@ -239,15 +262,19 @@
# Time Complexity: O(1)
# @param elem Element to be pushed
# @param priority Priority of the element
- # @raise [ArgumentError] if the element is already in the heap
# @return [PairingHeap]
def push(elem, priority)
- node = Node.new(elem, priority, nil, nil)
- @root = meld(@root, node)
+ node = Node.new(elem, priority)
+ if @root
+ @root = meld(@root, node)
+ else
+ @root = node
+ end
@size += 1
self
end
alias enqueue push
+ alias offer push
# Returns the element at the top of the heap
# Time Complexity: O(1)
@@ -256,6 +283,10 @@
end
def peek_priority
+ @root&.priority
+ end
+
+ def peek_with_priority
[@root&.elem, @root&.priority]
end
@@ -278,20 +309,18 @@
end
alias length size
- # Removes element from the top of the heap
+ # Removes element from the top of the heap and returns it
# Time Complexity: O(N)
# Amortized time Complexity: O(log(N))
# @raise [ArgumEntError] if the heap is empty
- # @return [PairingHeap]
def pop
raise ArgumentError, "Cannot remove from an empty heap" if @root.nil?
@size -= 1
elem = @root.elem
@root = merge_pairs(@root.subheaps)
- if @root
- @root.next_sibling = nil
- end
+ @root&.next_sibling = nil
+
elem
end
alias dequeue pop
@@ -299,6 +328,12 @@
def pop_priority
node = @root
pop
+ node.priority
+ end
+
+ def pop_with_priority
+ node = @root
+ pop
[node.elem, node.priority]
end
@@ -306,9 +341,6 @@
include MergePairs
def meld(left, right)
- return right if left.nil?
- return left if right.nil?
-
if @order[left.priority, right.priority]
parent = left
child = right
@@ -350,7 +382,7 @@
# Changes a priority of the element to a more prioritary one
# Time Complexity: O(N)
# Amortized Time Complexity: O(log(N))
- # @raise [ArgumentError] if the element heap is not in the heap
+ # @raise [ArgumentError] if the element is not in the heap
# @return [PairingHeap]
def change_priority(elem, priority)
raise ArgumentError, "Provided element is not in heap" unless
@nodes.key?(elem)
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/metadata new/metadata
--- old/metadata 2022-02-08 20:45:24.000000000 +0100
+++ new/metadata 2022-09-04 21:41:24.000000000 +0200
@@ -1,14 +1,14 @@
--- !ruby/object:Gem::Specification
name: pairing_heap
version: !ruby/object:Gem::Version
- version: 0.3.0
+ version: 1.0.0
platform: ruby
authors:
- Marcin Henryk Bartkowiak
autorequire:
bindir: exe
cert_chain: []
-date: 2022-02-08 00:00:00.000000000 Z
+date: 2022-09-04 00:00:00.000000000 Z
dependencies:
- !ruby/object:Gem::Dependency
name: minitest
