A heap is a specialized tree-based data structure that satisfies the heap property.If Y is the child node of X,then key(X) >= key(Y). Such a heap is called a max heap and the opposite one is called a min heap.
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
Search Your Question
Tuesday, July 22, 2008
Heaps And Heapsort
Labels:
Data Structures
Subscribe to:
Post Comments (Atom)
Archives
-
▼
2008
(992)
-
▼
July
(288)
- Yahoo Interview
- Yahoo Interview Questions
- Yahoo Interview Questions-1
- Yahoo Interview Questions-2
- Visual Basic Interview Questions -7
- Visual Basic Interview Questions -6
- Visual Basic Interview Questions -5
- Visual Basic Interview Questions -4
- Visual Basic Interview Questions -3
- Visual Basic Interview Questions -2
- Visual Basic Interview Questions -1
- SQL Interview Questions -8
- SQL Interview Questions -7
- SQL Interview Questions -6
- SQL Interview Questions -5
- SQL Interview Questions -4
- SQL Interview Questions -3
- SQL Interview Questions -2
- SQl Job Interview Questions
- Solutions to C programming questions
- Modified Array based QuickSort with respect to the...
- Last Non Zero Digit of Factorial
- Quick Sort routine to find the kth smallest elemen...
- Run time Analysis of QuickSort ,Nature of Input,Pi...
- Tree Arithmetic
- Number of ways to express a number as summation of...
- Solutions to Logical Puzzles-2
- Combinations
- Solutions to Basic C Interview Questions
- Solutions to Logical Puzzles-1
- Solutions to Logical Puzzles-3
- C program to find the height of a binary search tree
- C program to determine the number of nodes in a bi...
- C program to delete a tree
- Minimum Value of a Binary Search Tree
- Solutions to Questions on recursion
- C program to create mirror copy of a tree
- Solutions to Amazon Intern Interview Questions
- Traversals of a Binary Tree
- Solutions to Google Top Interview Puzzles
- Solutions to problems in recursion analysis
- solution1
- C-program to make a copy of a tree
- C-program to check whether a binary tree is a Bina...
- C-program to delete a node from a tree
- Search On a Binary Search Tree
- C-program to count the leaves in a tree
- Some Basic Questions on sorting and their solutions
- Resume Tips
- Secrets of a Selling Resume
- The Three R's of Resume Writing
- Top Ten Pitfalls of a Resume
- Ten Tips for Writing Better Resumes
- Frequently Asked Questions - Object oriented Concepts
- Frequently Asked Questions - Operating System Conc...
- Frequently Asked Questions - Database
- Frequently Asked Questions - Networking
- UNIX Concepts
- Resources For Placements Preparation
- Essentials Of Operating Systems
- Networking Concepts
- Microsoft Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Practise Puzzles - 1
- Practise Puzzles - 1
- Practise Puzzles - 2
- Practise Puzzles - 2
- Practise Puzzles - 2
- Answers For Practise Puzzles - 1
- Answers for Practise Puzzles - 2
- Practise Puzzles - 3
- Practise Puzzles - 3
- Practise Puzzles - 3
- Answers for Practise Puzzles - 3
- Practise Puzzles - 4
- Practise Puzzles - 4
- Answers For Practice Puzzles - 4
- Puzzles
- Logical Puzzles-1
- Logical Puzzles -2
- Logical Puzzles-3
- Algorithms And Programming #4
- Algorithms And Programming #5
- Algorithms And Programming #6
- Algorithms And Programming #7
- Algorithms And Programming #8
- Algorithms And Programming #9
- Prime Numbers!
- C Programming Puzzles
- C Programming Puzzles 2
- C Programming Puzzles 3
- C Programming Puzzles 4
-
▼
July
(288)
No comments:
Post a Comment