The operations commonly performed with a heap are:

1)delete-max or delete-min:removing the root node of a max or min-heap,respectively.

2)increase-key or decrease-key:updating a key within a max or min-heap,respectively.

3)merge:joining two heaps to form a valid new heap containing all the elements of both.

Heaps are used in the sorting algorithm called heapsort.

**HEAPSORT:**

Heap sort is one of the best methods being in-place and with no quadratic worst case scenarios.It is a comparision based sorting algorithm, ans is part of the selection sort family.The operations performed by heap sort algorithm are:

**BUILD-MAX-HEAP:**To build a max heap with the given [1,n] elements.

**MAX-HEAPIFY:**Which modifies a heap with [1,n-1] elements so that it satifies the properties of a heap.

The following are the basic questions on heaps:

1)What are the properties of a heap?

2)What is the height of an n-element heap?

3)Where in a max-heap might the smallest element reside, assuming that all the elements are distinct?

4)Is an array that is in sorted order a min-heap?

5)What are the minimum and maximum numbers of elements in a heap of height h?

6)How many nodes are present in an n-element heap of height h?

7)What is the running time complexity of a heapsort?

8)What is the worst-case running time of a heapsort?

9)What is the running time of heapsort on an array A of length n that is alreay sorted in increasing order? What about the same in decreasing order?

10)What is the best case running time of heapsort when all the elements are distinct?

11)Name some applications of heaps

Nice :) thank u

ReplyDeleteThese look very similar to those exercises in CLRS

ReplyDeleteHi,

ReplyDeleteI have explained heaps algorithms and coded them here.

Heaps

Great and Useful Article.

ReplyDeleteJava Online Training

Online Java Course

Java Course Online

J2EE training

online J2EE training

Best Recommended books for Spring framework

Java Interview Questions

Java Training Institutes in Chennai

Java Training in Chennai

J2EE Training in Chennai

java j2ee training institutes in chennai

Java Course in Chennai