Questions tagged [decrease-key]
12 questions
60
votes
4 answers
How to implement O(logn) decrease-key operation for min-heap based Priority Queue?
I am working on an application that demonstrates the Djikstra's algorithm, and to use it, I need to restore the heap property when my elements' value is decreased.
The problem regarding the complexity is that when the algorithm changes the value of…
jathanasiou
- 882
- 2
- 8
- 17
8
votes
2 answers
An ordered dictionary supporting decrease-key?
Many fast priority queues (such as the Fibonacci heap and pairing heap) support a decrease-key operation, which takes an element already stored in the priority queue and efficiently decreases its priority. In the case of the Fibonacci and pairing…
templatetypedef
- 362,284
- 104
- 897
- 1,065
4
votes
4 answers
Implement decreaseKey in STL Priority Queue C++
I'm trying to implement Prim's Algorithm and for that I need to have a decreaseKey method for a priority queue (to update the key value in a priority queue). Can I implement this in the STL Priority Queue?
If it helps, this is the algorithm I'm…
user1641700
- 53
- 3
- 9
3
votes
1 answer
Binomial Heap implementation in Python 2.7
I'm looking for a Python implementation of Binomial Heap and I noticed that the codes don't have decreaseKey implemented. Why in Binomial Heap nobody implements decreaseKey?
Roberto Pavia
- 75
- 7
3
votes
3 answers
Why does decreasekey in Dijkstra's algorithm take O(logN) time?
for the updating part,
for all neighbors w of u:
if dist[w] > dist[u] + l(u,w)
dist[w] = dist[u] + l(u,w)
prev[w] = u
decreasekey(H,w)
Here, w is the ID of the node, I think it should be like pair(ID,key) which key is…
yw_maggie
- 43
- 4
3
votes
1 answer
How to make decrease-key in binomial heap run in logarithm time
The interface provided by the book "Introduction to Algorithm" of decreasing key in binomial heap is:
BINOMIAL-HEAP-DECREASE-KEY (H,x,k), where H is the pointer to the first root of the tree, x is the "index" of the node, whose key is to be…
Yiliang
- 463
- 2
- 6
- 16
2
votes
2 answers
Why Java's Priority Queue lacks a Change Priority method?
I was wondering why Java's Priority Queue does not support the ChangePriority. I have read somewhere (with no details) that dropping ChangePriority allows one to use more efficient implementation, but have no idea how it could be possible - binary…
Domin
- 141
- 6
1
vote
1 answer
Decrease operation in fibonacci heap, boost
I'm trying to use in my implementation the fibonacci heap from boost but my program crashes, when I calling decrease function, this the example (W is a simple class):
struct heap_data
{
boost::heap::fibonacci_heap::handle_type…
Vincenty
- 11
- 2
1
vote
1 answer
How to implement decrease-key in a Fibonacci heap to run in O(1) amortized time?
How can you get O(1) amortized complexity in the decrease-key operation on a Fibonacci heap? Just finding the node in the Fibonacci heap that contains the element takes O(n) time using a BFS, which should make it impossible to get O(1) amortized…
Rohit Garg
- 115
- 2
- 10
0
votes
1 answer
What is a decrease key operation for doubly linked list?
I came across this data structure description on Gate overflow:
items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the…
Neel Joshi
- 37
- 4
0
votes
2 answers
how to arrange an array in decreasing order
I have a simple code to iterate over all the elements within the range
for i in range(5,10):
print(i)
#output
5
6
7
8
9
Now, would it be possible to iterate the same elements from 10 to 5 in the decreasing order ?
By changing the range in the…
vashista
- 105
- 7
0
votes
0 answers
Why does committed heap memory decrease from 4G to 3.86G?
Tomcat runs in a virtual machine. I monitored a sudden decrease in the JVM committed heap memory from 4G to 3.86G. This causes FULL GC. I want to know why and when JVM does it?
litterdu
- 1