Heaps
Abstract
To implement Prim's algorithm efficiently, we need a data structure that will store the vertices of S in a way that allows the vertex joined by the minimum cost edge to be selected quickly.1.A heap is a data structure consisting of a collection of items, each having a key. The basic operations on a heap are:
" insert(i,k,h). Add item i to heap h using k as the key value.
" deletemin(h). Delete and return an item of minimum key from h.
" changekey(i,k,h). Change the key of item i in heap h to k.
" key(i,h). Return the key value for item i.
Description of Heaps
2.The heap is among the most widely applicable non-elementary data
structure.
3.Heaps can be implemented efficiently, using a heap-ordered tree.
" each tree node contains one item and each item has a real-valued key
" the key of each node is at least as large the key of its parent (excepting the root)
4.The depth of a d-heap with n nodes is logdn .
5.The nodes of a d-heap can be stored in an array in breadth-first order.
" allows indices for parents and children to calculated directly, eliminating the need for pointers.
The Heap Data Structure
To implement Prim's algorithm efficiently, we need a data structure that will store the vertices of S in a way that allows the vertex joined by the minimum cost edge to be selected quickly.
1.A heap is a data structure consisting of a collection of items, each having a key. The basic operations on a heap are:
" insert(i,k,h). Add item i to heap h using k as the key value.
" deletemin(h). Delete and return an item of minimum key from h.
" changekey(i,k,h). Change the key of item i in heap h to k.
" key(i,h). Return the key value for item i.
2.The heap is among the most widely applicable non-elementary data structure.
3.Heaps can be implemented efficiently, using a heap-ordered tree.
" each tree node contains one item and each item has a real-valued key
" the key of each node is at least as large the key of its parent (excepting the root)
4.The depth of a d-heap with n nodes is logdn .
5.The nodes of a d-heap can be stored in an array in breadth-first order.
" allows indices for parents and children to calculated directly, eliminating the
need for pointers
6.When the key of an item is decreased, we can restore heap-order, by repeatedly swapping the item with its parent.
7.Similarly, for increasing an item's key.
8.The heap operation meld(h1,h2), which combines the two heaps h1 and h2 and returns the resulting heap can't be implemented efficiently using d-heaps but can be with an alternative heap implementation known as a leftist heap.
9.The Fibonacci heap data structure provides an efficient implementation of a collection of heaps.
10.Items in the heaps are integers over {1, . . . ,n}. Each item has a key.
11.Each non-empty heap is identified by one of its members (its id).
Initially, there are no heaps.is id
