Good C++ data structure implementation of *min-heap* augmented with *hash table* [closed]

Good C++ data structure implementation of min-heap augmented with hash table [closed]

up vote
-3
down vote

favorite

I am looking an efficient C++ data structure implementation of min-heap augmented with hash table.

There is a counter-part in python which called pqdict.
Priority Queue Dictionary — pqdict 1.0.0 documentation
https://pqdict.readthedocs.io/

To be more specific, I want to use this data structure as the open list for an efficient a* search implementation.

I hope there already exists one so I do not need to re-implement.

asked Nov 20 at 2:45

ayuka

closed as off-topic by Passer By, Drew Dormann, rsjaffe, Jeremy Friesner, Baum mit Augen Nov 25 at 21:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

"Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Passer By, Drew Dormann, rsjaffe, Jeremy Friesner, Baum mit Augen

If this question can be reworded to fit the rules in the help center, please edit the question.

The performance is no different from a regular pq, so how much efficiency are you really expecting to get by switching to this kind of queue?
– smac89
Nov 20 at 2:59

Also, this pqdict is essentially the same as using python's heapq with a tuple where the first element is the priority of the second element
– smac89
Nov 20 at 3:01

@smac89 I am not expecting to have better heap performance. The objective to support two types of operations: 1. heap related, log(n) insert, sorted use key1; 2. query related, log(1) query, use a different key2.
– ayuka
Nov 21 at 1:25

add a comment |

up vote
-3
down vote

favorite

I am looking an efficient C++ data structure implementation of min-heap augmented with hash table.

There is a counter-part in python which called pqdict.
Priority Queue Dictionary — pqdict 1.0.0 documentation
https://pqdict.readthedocs.io/

To be more specific, I want to use this data structure as the open list for an efficient a* search implementation.

I hope there already exists one so I do not need to re-implement.

asked Nov 20 at 2:45

ayuka

closed as off-topic by Passer By, Drew Dormann, rsjaffe, Jeremy Friesner, Baum mit Augen Nov 25 at 21:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

"Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Passer By, Drew Dormann, rsjaffe, Jeremy Friesner, Baum mit Augen

If this question can be reworded to fit the rules in the help center, please edit the question.

The performance is no different from a regular pq, so how much efficiency are you really expecting to get by switching to this kind of queue?
– smac89
Nov 20 at 2:59

Also, this pqdict is essentially the same as using python's heapq with a tuple where the first element is the priority of the second element
– smac89
Nov 20 at 3:01

@smac89 I am not expecting to have better heap performance. The objective to support two types of operations: 1. heap related, log(n) insert, sorted use key1; 2. query related, log(1) query, use a different key2.
– ayuka
Nov 21 at 1:25

add a comment |

up vote
-3
down vote

favorite

I am looking an efficient C++ data structure implementation of min-heap augmented with hash table.

There is a counter-part in python which called pqdict.
Priority Queue Dictionary — pqdict 1.0.0 documentation
https://pqdict.readthedocs.io/

To be more specific, I want to use this data structure as the open list for an efficient a* search implementation.

I hope there already exists one so I do not need to re-implement.

asked Nov 20 at 2:45

ayuka

I am looking an efficient C++ data structure implementation of min-heap augmented with hash table.

There is a counter-part in python which called pqdict.
Priority Queue Dictionary — pqdict 1.0.0 documentation
https://pqdict.readthedocs.io/

To be more specific, I want to use this data structure as the open list for an efficient a* search implementation.

I hope there already exists one so I do not need to re-implement.

c++ data-structures

asked Nov 20 at 2:45

ayuka

asked Nov 20 at 2:45

ayuka

asked Nov 20 at 2:45

ayuka

asked Nov 20 at 2:45

ayuka

asked Nov 20 at 2:45

ayuka

closed as off-topic by Passer By, Drew Dormann, rsjaffe, Jeremy Friesner, Baum mit Augen Nov 25 at 21:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

"Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Passer By, Drew Dormann, rsjaffe, Jeremy Friesner, Baum mit Augen

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by Passer By, Drew Dormann, rsjaffe, Jeremy Friesner, Baum mit Augen Nov 25 at 21:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

"Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – Passer By, Drew Dormann, rsjaffe, Jeremy Friesner, Baum mit Augen

If this question can be reworded to fit the rules in the help center, please edit the question.

The performance is no different from a regular pq, so how much efficiency are you really expecting to get by switching to this kind of queue?
– smac89
Nov 20 at 2:59

Also, this pqdict is essentially the same as using python's heapq with a tuple where the first element is the priority of the second element
– smac89
Nov 20 at 3:01

@smac89 I am not expecting to have better heap performance. The objective to support two types of operations: 1. heap related, log(n) insert, sorted use key1; 2. query related, log(1) query, use a different key2.
– ayuka
Nov 21 at 1:25

add a comment |

The performance is no different from a regular pq, so how much efficiency are you really expecting to get by switching to this kind of queue?
– smac89
Nov 20 at 2:59

Also, this pqdict is essentially the same as using python's heapq with a tuple where the first element is the priority of the second element
– smac89
Nov 20 at 3:01

@smac89 I am not expecting to have better heap performance. The objective to support two types of operations: 1. heap related, log(n) insert, sorted use key1; 2. query related, log(1) query, use a different key2.
– ayuka
Nov 21 at 1:25

The performance is no different from a regular pq, so how much efficiency are you really expecting to get by switching to this kind of queue?
– smac89
Nov 20 at 2:59

Also, this pqdict is essentially the same as using python's heapq with a tuple where the first element is the priority of the second element
– smac89
Nov 20 at 3:01

@smac89 I am not expecting to have better heap performance. The objective to support two types of operations: 1. heap related, log(n) insert, sorted use key1; 2. query related, log(1) query, use a different key2.
– ayuka
Nov 21 at 1:25

add a comment |

1 Answer
1

active

oldest

votes

up vote
1
down vote

I assume you want this kind of data structure to support the decrease_key operation...

When I implement A* or Dijkstra's algorithm, I just don't do it that way.

In C++, I would:

put (node *,priority) records in a std::priority_queue, and also store the priorities in the nodes.

When decreasing the priority in a node, just insert another record into the priority queue and leave the old one where it is.

When popping a record off the priority queue, check to see if the priority is accurate. If it isn't then discard it and pop again.

Keep track of the number of invalid records in the priority queue. When/if the number of invalid records grows to half the size of the priority queue, then clear and rebuild the priority queue with only valid records.

This sort of system is easy to implement, doesn't affect the complexity of Dijkstra's algorithm or A*, and uses less memory than most of the kinds of data structure you're asking for.

edited Nov 20 at 5:05

answered Nov 20 at 5:00

Matt Timmermans

18.1k11532

I guess peek also has to pop if the priority is inaccurate - but if you allow bad records to grow to 50% of the heap size peek is no longer O(1) (as a standalone operation, though it may be as amoritized over (a lot) more peeks than pops). Meanwhile, the rebuild takes O(n lg n) when you need it, right? Plus temporarily uses more memory? I should say it seems the improvement (besides less memory) is in the constants hidden by O() notation - not having to update the heap and the index? Your suggested data structure is interesting - do you have a repo somewhere?
– davidbak
Nov 20 at 5:15

The pops and rebuilding are both just paying the amortized O(log n) cost of each decrease_key, and you should be able to arrange things so that you can do the rebuild in place (and usually in O(n), but that's not necessary). I don't think I've done this in OSS, so sorry no repo.
– Matt Timmermans
Nov 20 at 13:30

@MattTimmermans Could you please explain a bit more about "the priority is accurate"? I think if I have duplicated nodes (position-wise) in the open list, I need to check if the popped node already exists in the closed list every time right? Then I should have a hashtable like close list which I can efficiently query if a position-based key exits in the table.
– ayuka
Nov 20 at 15:53

@ayuka You store the priority in the nodes and in the records. You only insert a new record for the node when the priority is decreased, so there is only ever one record for each node,priority combination. When you pop a record you just check record.priority == record.node->priority to see if the record is the valid one for that node.
– Matt Timmermans
Nov 20 at 18:48

add a comment |

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

up vote
1
down vote

I assume you want this kind of data structure to support the decrease_key operation...

When I implement A* or Dijkstra's algorithm, I just don't do it that way.

In C++, I would:

put (node *,priority) records in a std::priority_queue, and also store the priorities in the nodes.

When decreasing the priority in a node, just insert another record into the priority queue and leave the old one where it is.

When popping a record off the priority queue, check to see if the priority is accurate. If it isn't then discard it and pop again.

Keep track of the number of invalid records in the priority queue. When/if the number of invalid records grows to half the size of the priority queue, then clear and rebuild the priority queue with only valid records.

This sort of system is easy to implement, doesn't affect the complexity of Dijkstra's algorithm or A*, and uses less memory than most of the kinds of data structure you're asking for.

edited Nov 20 at 5:05

answered Nov 20 at 5:00

Matt Timmermans

18.1k11532

I guess peek also has to pop if the priority is inaccurate - but if you allow bad records to grow to 50% of the heap size peek is no longer O(1) (as a standalone operation, though it may be as amoritized over (a lot) more peeks than pops). Meanwhile, the rebuild takes O(n lg n) when you need it, right? Plus temporarily uses more memory? I should say it seems the improvement (besides less memory) is in the constants hidden by O() notation - not having to update the heap and the index? Your suggested data structure is interesting - do you have a repo somewhere?
– davidbak
Nov 20 at 5:15

The pops and rebuilding are both just paying the amortized O(log n) cost of each decrease_key, and you should be able to arrange things so that you can do the rebuild in place (and usually in O(n), but that's not necessary). I don't think I've done this in OSS, so sorry no repo.
– Matt Timmermans
Nov 20 at 13:30

@MattTimmermans Could you please explain a bit more about "the priority is accurate"? I think if I have duplicated nodes (position-wise) in the open list, I need to check if the popped node already exists in the closed list every time right? Then I should have a hashtable like close list which I can efficiently query if a position-based key exits in the table.
– ayuka
Nov 20 at 15:53

@ayuka You store the priority in the nodes and in the records. You only insert a new record for the node when the priority is decreased, so there is only ever one record for each node,priority combination. When you pop a record you just check record.priority == record.node->priority to see if the record is the valid one for that node.
– Matt Timmermans
Nov 20 at 18:48

add a comment |

up vote
1
down vote

I assume you want this kind of data structure to support the decrease_key operation...

When I implement A* or Dijkstra's algorithm, I just don't do it that way.

In C++, I would:

put (node *,priority) records in a std::priority_queue, and also store the priorities in the nodes.

When decreasing the priority in a node, just insert another record into the priority queue and leave the old one where it is.

When popping a record off the priority queue, check to see if the priority is accurate. If it isn't then discard it and pop again.

Keep track of the number of invalid records in the priority queue. When/if the number of invalid records grows to half the size of the priority queue, then clear and rebuild the priority queue with only valid records.

This sort of system is easy to implement, doesn't affect the complexity of Dijkstra's algorithm or A*, and uses less memory than most of the kinds of data structure you're asking for.

edited Nov 20 at 5:05

answered Nov 20 at 5:00

Matt Timmermans

18.1k11532

I guess peek also has to pop if the priority is inaccurate - but if you allow bad records to grow to 50% of the heap size peek is no longer O(1) (as a standalone operation, though it may be as amoritized over (a lot) more peeks than pops). Meanwhile, the rebuild takes O(n lg n) when you need it, right? Plus temporarily uses more memory? I should say it seems the improvement (besides less memory) is in the constants hidden by O() notation - not having to update the heap and the index? Your suggested data structure is interesting - do you have a repo somewhere?
– davidbak
Nov 20 at 5:15

The pops and rebuilding are both just paying the amortized O(log n) cost of each decrease_key, and you should be able to arrange things so that you can do the rebuild in place (and usually in O(n), but that's not necessary). I don't think I've done this in OSS, so sorry no repo.
– Matt Timmermans
Nov 20 at 13:30

@MattTimmermans Could you please explain a bit more about "the priority is accurate"? I think if I have duplicated nodes (position-wise) in the open list, I need to check if the popped node already exists in the closed list every time right? Then I should have a hashtable like close list which I can efficiently query if a position-based key exits in the table.
– ayuka
Nov 20 at 15:53

@ayuka You store the priority in the nodes and in the records. You only insert a new record for the node when the priority is decreased, so there is only ever one record for each node,priority combination. When you pop a record you just check record.priority == record.node->priority to see if the record is the valid one for that node.
– Matt Timmermans
Nov 20 at 18:48

add a comment |

up vote
1
down vote

I assume you want this kind of data structure to support the decrease_key operation...

When I implement A* or Dijkstra's algorithm, I just don't do it that way.

In C++, I would:

put (node *,priority) records in a std::priority_queue, and also store the priorities in the nodes.

When decreasing the priority in a node, just insert another record into the priority queue and leave the old one where it is.

When popping a record off the priority queue, check to see if the priority is accurate. If it isn't then discard it and pop again.

Keep track of the number of invalid records in the priority queue. When/if the number of invalid records grows to half the size of the priority queue, then clear and rebuild the priority queue with only valid records.

This sort of system is easy to implement, doesn't affect the complexity of Dijkstra's algorithm or A*, and uses less memory than most of the kinds of data structure you're asking for.

edited Nov 20 at 5:05

answered Nov 20 at 5:00

Matt Timmermans

18.1k11532

I assume you want this kind of data structure to support the decrease_key operation...

When I implement A* or Dijkstra's algorithm, I just don't do it that way.

In C++, I would:

put (node *,priority) records in a std::priority_queue, and also store the priorities in the nodes.

When decreasing the priority in a node, just insert another record into the priority queue and leave the old one where it is.

When popping a record off the priority queue, check to see if the priority is accurate. If it isn't then discard it and pop again.

Keep track of the number of invalid records in the priority queue. When/if the number of invalid records grows to half the size of the priority queue, then clear and rebuild the priority queue with only valid records.

This sort of system is easy to implement, doesn't affect the complexity of Dijkstra's algorithm or A*, and uses less memory than most of the kinds of data structure you're asking for.

edited Nov 20 at 5:05

answered Nov 20 at 5:00

Matt Timmermans

18.1k11532

edited Nov 20 at 5:05

answered Nov 20 at 5:00

Matt Timmermans

18.1k11532

answered Nov 20 at 5:00

Matt Timmermans

18.1k11532

answered Nov 20 at 5:00

Matt Timmermans

18.1k11532

I guess peek also has to pop if the priority is inaccurate - but if you allow bad records to grow to 50% of the heap size peek is no longer O(1) (as a standalone operation, though it may be as amoritized over (a lot) more peeks than pops). Meanwhile, the rebuild takes O(n lg n) when you need it, right? Plus temporarily uses more memory? I should say it seems the improvement (besides less memory) is in the constants hidden by O() notation - not having to update the heap and the index? Your suggested data structure is interesting - do you have a repo somewhere?
– davidbak
Nov 20 at 5:15

The pops and rebuilding are both just paying the amortized O(log n) cost of each decrease_key, and you should be able to arrange things so that you can do the rebuild in place (and usually in O(n), but that's not necessary). I don't think I've done this in OSS, so sorry no repo.
– Matt Timmermans
Nov 20 at 13:30

@MattTimmermans Could you please explain a bit more about "the priority is accurate"? I think if I have duplicated nodes (position-wise) in the open list, I need to check if the popped node already exists in the closed list every time right? Then I should have a hashtable like close list which I can efficiently query if a position-based key exits in the table.
– ayuka
Nov 20 at 15:53

@ayuka You store the priority in the nodes and in the records. You only insert a new record for the node when the priority is decreased, so there is only ever one record for each node,priority combination. When you pop a record you just check record.priority == record.node->priority to see if the record is the valid one for that node.
– Matt Timmermans
Nov 20 at 18:48

add a comment |

I guess peek also has to pop if the priority is inaccurate - but if you allow bad records to grow to 50% of the heap size peek is no longer O(1) (as a standalone operation, though it may be as amoritized over (a lot) more peeks than pops). Meanwhile, the rebuild takes O(n lg n) when you need it, right? Plus temporarily uses more memory? I should say it seems the improvement (besides less memory) is in the constants hidden by O() notation - not having to update the heap and the index? Your suggested data structure is interesting - do you have a repo somewhere?
– davidbak
Nov 20 at 5:15

The pops and rebuilding are both just paying the amortized O(log n) cost of each decrease_key, and you should be able to arrange things so that you can do the rebuild in place (and usually in O(n), but that's not necessary). I don't think I've done this in OSS, so sorry no repo.
– Matt Timmermans
Nov 20 at 13:30

@MattTimmermans Could you please explain a bit more about "the priority is accurate"? I think if I have duplicated nodes (position-wise) in the open list, I need to check if the popped node already exists in the closed list every time right? Then I should have a hashtable like close list which I can efficiently query if a position-based key exits in the table.
– ayuka
Nov 20 at 15:53

@ayuka You store the priority in the nodes and in the records. You only insert a new record for the node when the priority is decreased, so there is only ever one record for each node,priority combination. When you pop a record you just check record.priority == record.node->priority to see if the record is the valid one for that node.
– Matt Timmermans
Nov 20 at 18:48

I guess peek also has to pop if the priority is inaccurate - but if you allow bad records to grow to 50% of the heap size peek is no longer O(1) (as a standalone operation, though it may be as amoritized over (a lot) more peeks than pops). Meanwhile, the rebuild takes O(n lg n) when you need it, right? Plus temporarily uses more memory? I should say it seems the improvement (besides less memory) is in the constants hidden by O() notation - not having to update the heap and the index? Your suggested data structure is interesting - do you have a repo somewhere?
– davidbak
Nov 20 at 5:15

The pops and rebuilding are both just paying the amortized O(log n) cost of each decrease_key, and you should be able to arrange things so that you can do the rebuild in place (and usually in O(n), but that's not necessary). I don't think I've done this in OSS, so sorry no repo.
– Matt Timmermans
Nov 20 at 13:30

@MattTimmermans Could you please explain a bit more about "the priority is accurate"? I think if I have duplicated nodes (position-wise) in the open list, I need to check if the popped node already exists in the closed list every time right? Then I should have a hashtable like close list which I can efficiently query if a position-based key exits in the table.
– ayuka
Nov 20 at 15:53

@ayuka You store the priority in the nodes and in the records. You only insert a new record for the node when the priority is decreased, so there is only ever one record for each node,priority combination. When you pop a record you just check record.priority == record.node->priority to see if the record is the valid one for that node.
– Matt Timmermans
Nov 20 at 18:48

add a comment |

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Tukukkk