## Heaps

Published on Nov 06, 2015

### Abstract

#### 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.i

#### More Seminar Topics:

Active Appearance Models,
1XEV-DO Architecture For Wireless Internet,
Hyper Transport Technology,
Honeypot,
Heaps,
Generic Visual Perception Processor GVPP,
Foveon X3,
EXTENSIBLE FIRMWARE INTERFACE,
Efficient Implementation Of Cryptographically Useful"Large"Boolean Functions,
Dynamically Reconfigurability Computing,
Data Security In Wireless Networks,
Cellular through Remote Control Switch,
Border Security using Wireless Integrated Network Sensors,
An ATM With An Eye,
Stream Processor,
Smart Edit,
Real- Time Systems and Real- Time Operating Systems,
PLATONIS,
M-Voting,
CBSE Plus Two Results 2016,
E Ball PC Technology,
Cyber Crime,
Adaptive Control System