Search code examples
algorithmstructureheapprims-algorithm

heap structure with prim's

I want to ask about what are the interest of use heap structure with prim's algorithm ? As in the assignment: "Since the heap structure you implement will be used for a Prim’s algorithm" Thank you !

Solution

  • Prim`s Algorithm is similar to graph traversal technique : BFS, (rather Its better to say it uses BFS). A queue is needed in BFS.

    Normal queue data structure asneeded by simple BFS is first in first out. For Prim`s this behavior of queue needs to be modified.

    Instead of first in first out, the data structure needs to pick minimum valued element from the elements it holds. The operations needed by Prim's algorithm for the underlying data structure must support

    1. new insertions

    2. modifications to the value of element already put in the data structure.

    3. Pick (and remove) minimum of the items already contained in the data structure.

    These operations could be efficiently be implemented by Min-Heap. For simplicity binary heap is used and for more efficiency Fibonacci heap may be used.