Applications of Heaps(Anecdotal perspective)
Hi guys,
My favorite data structure is probably a heap, although I've never implemented it in a proper project rather small beginner programs. From past experiences do you recall a scenario where you used a heap in a major project to help solve a problem? If so please do give some examples and anecdotes.
Thanks :)
My favorite data structure is probably a heap, although I've never implemented it in a proper project rather small beginner programs. From past experiences do you recall a scenario where you used a heap in a major project to help solve a problem? If so please do give some examples and anecdotes.
Thanks :)
What do you mean by 'data structure'? 'heap' is rather an sorting algorithm.
I'm using it when it comes to priority. E.g. when drawing objects. The advantage is that the order remains the same unless an object has a higher priority.
I'm using it when it comes to priority. E.g. when drawing objects. The advantage is that the order remains the same unless an object has a higher priority.
closed account (z05DSL3A)
| coder777 wrote: |
|---|
| What do you mean by 'data structure'? |
https://en.wikipedia.org/wiki/Heap_(data_structure)
If you consider priority queue as a data structure. No I don't use it. Rather a vector and applying the heap function to it, like:
http://www.cplusplus.com/reference/algorithm/make_heap/
etc.
It is more flexible/easier to handle in my case.
http://www.cplusplus.com/reference/algorithm/make_heap/
etc.
It is more flexible/easier to handle in my case.
closed account (z05DSL3A)
| coder777 wrote: |
|---|
| If you consider priority queue as a data structure. |
I guess I consider a priority queue as an abstract data type that is often implemented with a heap.
I guess I use heaps a lot indirectly but can't remember the last time I specifically implemented something using a heap data structure.
I can't recall the last time I used a non-stl home rolled data structure period, not counting assisting homework here.
Heaps seem to do what they were designed to do well. I suspect that, like a tree, if you shovel it into a vector (using indices as the 'pointers') it can do both the heapish tasks and vectorish tasks making it quite efficient at a variety of things.
Heaps seem to do what they were designed to do well. I suspect that, like a tree, if you shovel it into a vector (using indices as the 'pointers') it can do both the heapish tasks and vectorish tasks making it quite efficient at a variety of things.
The only time I used a heap was to implement a priority queue in a simulator. This was before the STL.
The simulator processes events. Each event has a timestamp for when the event should happen (in simulator time) and the priority queue is sorted by timestamp. The simulator just picks the first item off the heap, executes it, and repeats. Executing an event usually generates other events that will occur in the future, so those get put into the heap.
The simulator processes events. Each event has a timestamp for when the event should happen (in simulator time) and the priority queue is sorted by timestamp. The simulator just picks the first item off the heap, executes it, and repeats. Executing an event usually generates other events that will occur in the future, so those get put into the heap.
Topic archived. No new replies allowed.