Stack Overflow
Stack Overflow

Questions tagged [pairing-heap]

A pairing heap is a self-adjusting heap data structure that efficiently supports decrease-key.

The pairing heap was introduced by Fredman, Sedgewick, Sleator, and Tarjan in their paper The Pairing Heap, a New Form of Self-Adjusting Heap. It has worse theoretical performance than the more complicated Fibonacci Heap, but in practice is dramatically faster.

11 questions
8
votes
1 answer

Why does pairing heap need that special two passes when delete_min?

I am reading the Pairing heap. It is quite simple, the only tricky part is the delete_min operation. The only non-trivial fundamental operation is the deletion of the minimum element from the heap. The standard strategy first merges the …
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271
6
votes
1 answer

Pairing heap - implementation of decrease key

I just implemented the pairing heap data structure. Pairing heap supports insert, find-min, merge in O(1) amortized time and delete, delete-min in O(logN) amortized time. But the most remarkable operation is the decrease-key, which has complexity…
Rontogiannis Aristofanis
  • 8,883
  • 8
  • 41
  • 58
3
votes
1 answer

Android Bluetooth Paring Input Device

I am trying to make a pairing by code and it works only for normal devices. If I use a bluetooth scanner it pairs with it but the device doesn't work till I go to android settings and select the Input Device checkbox. How can I do this by…
Mihai Gabriel Petrescu
  • 41
  • 7
2
votes
2 answers

Slow worker thread performance with priority queue

I was attempting to use worker threads to speed up a larger algorithm when I noticed that using independent priority queue's on more threads actually slowed performance down. So I wrote a small test case. In which I query how many threads to start,…
Tocs
  • 752
  • 4
  • 17
1
vote
1 answer

Efficient algorithm for finding N min values in a min pairing-heap

I'm using the pairing heap implementation found here: https://github.com/jemalloc/jemalloc/commits/dev/include/jemalloc/internal/ph.h Once in a while though I need to iterate over the N min values in the heap (where N is bound by the number of…
hyrax
  • 139
  • 6
1
vote
1 answer

Pairing heaps - O(1) for decrease key?

I'm working on an assignment for one of my courses, and one question asks to show that the decrease-key operation, for a pairing heap, takes O(1) time. Obviously, if you have a pointer to the key you want to decrease, then the operation will take…
Asool
  • 13,031
  • 7
  • 35
  • 49
1
vote
1 answer

Hungarian algorithm in PHP with multiple assignments

In the following we are facing the problem of multiple assignments of the hungarian algorithm. Scenario: We have 100 students and 5 courses, which the students can vote with priority. So every student will get assigned for one specific…
Noli
  • 604
  • 2
  • 10
  • 27
1
vote
0 answers

CoreBluetooth first pairing read request fails

I wonder about a behavior in CoreBluetooth that i can see since i updated to iOS8.2 in. I think that it worked correctly in iOS 8.1 Situation: iPhone 6 iOS 8.2 working as CentralManager Custom BLE-Device (CC2541) Now...when i try to read a…
nivek
  • 151
  • 2
  • 7
1
vote
1 answer

(1 2 3 . #)- heapsort

I tried to implement a "pairing heap" with all the regular operations (merge, delete-min etc.), then I've been requested to write a function that would sort a list using my newly constructed heap implementation. Unfortunately it seems that someting…
superguay
  • 13
  • 3
0
votes
1 answer

Automatically increasing variable within a class

So, i'm coding one thing on c++, and i'm trying to implement a priority queue with pairing heaps. I want this priority to automatically increase over time, so that if the element (a class) has been in the heap for, say, 5 minutes, it's priority (a…
Noname
  • 85
  • 10
0
votes
0 answers

Pairing Heap - Implementation of Assignment Operator / Copy Constructor

I'm trying to implement a paring heap (https://en.wikipedia.org/wiki/Pairing_heap), but I seem to be having trouble writing the assignment operator and copy constructor. My default constructor as well as my push and pop functions seem to work. But…
brc1010
  • 11
  • 3