Definition of a heap

A heap is a data structure that contains objects which have comparable keys.

Some uses for a heap include: keeping track of employee records where the social security number is the key, network edges, events where there is a priority, etc.

Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes.

Heap ADT (Abstract Data Type)

There are two basic operations for a heap.

The running time for both operations is O(logn) where n is the number of objects in the heap. Some additional operations heap supports Another operation is heapify, which inserts a batch of objects into the heap. This seems like it should run in O(nlogn) but it can actually be done in O(n) by inserting the values in batch. Deletion can also be done in O(logn) time.

Implementing a heap

Conceptually,heap is an almost complete binary tree where the data (key) stored in a node is larger than those of its children nodes (i.e. concept of comparability) .

So, to understand heap, we have to see 2 views of heap - tree and array.

Heap must satisfy following properties :

Implementing the Operations of heap

Consider the operations one by one:

Cases when Implementing Binary heaps

Thanks.

Source

A heap is a data structure that contains objects which have comparable keys.

**Uses of Heap**Some uses for a heap include: keeping track of employee records where the social security number is the key, network edges, events where there is a priority, etc.

Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes.

Heap ADT (Abstract Data Type)

There are two basic operations for a heap.

- add a new object to the heap*Insert*

Running time - O (log n)- remove an object in the heap with a minimum key value (with ties broken arbitrarily). You could always makes this an extract-max operation or negate every key and you will get the maximum when you extract-min.*Extract-min*

Running time - O (log n)

**Other operations supported**- Initializes the heap in linear time i.e. O(n). Of-course you can use insert function, but then it will take O(log n) time per element, and so n log n time for n elements.**Heapify or BuildHeap**- You can delete any element from the heap in O (log n) time.**Delete**

The running time for both operations is O(logn) where n is the number of objects in the heap. Some additional operations heap supports Another operation is heapify, which inserts a batch of objects into the heap. This seems like it should run in O(nlogn) but it can actually be done in O(n) by inserting the values in batch. Deletion can also be done in O(logn) time.

Implementing a heap

Conceptually,heap is an almost complete binary tree where the data (key) stored in a node is larger than those of its children nodes (i.e. concept of comparability) .

So, to understand heap, we have to see 2 views of heap - tree and array.

**Tree view of heap**Heap must satisfy following properties :

- Heap is a binary tree - i.e. each node will have 0 or 1 or 2 children.
- Heap is almost complete tree - All nodes are filled in, except the last level may have some nodes missing toward the right. For eg. :

Almost Complete Binary Tree **Heap Property -**The key at any node is less than or equal to the keys of each of its children (if it has any). Because of this property, root of the minHeap is the smallest element.

So, at every node x

key[x] <= all keys of x's children

(Also, Except root, all the nodes do have the parent.)

Eg.

Though, heap property puts some ordering of structure, but in no way guarantees the order for given keys

**Array Implementation of Heap**Implementing the Operations of heap

Consider the operations one by one:

Cases when Implementing Binary heaps

**Immutability of Keys**- Assumption - Clients don't change the keys. So, better is to make the key class immutable. Like in Java - String, Integer, Double, Color, Vector, Transaction, Point2D are immutable, but these are mutable - StringBuilder, Stack, Counter, Java array.

Thanks.

Source

## 0 comments:

## Post a Comment