Design and Analysis of Algorithms
Selected Reading
- DAA - Discussion
- DAA - Useful Resources
- DAA - Quick Guide
- DAA - Hill Climbing Algorithm
- NP Hard & NP-Complete Classes
- DAA - Cook’s Theorem
- DAA - P and NP Class
- DAA - Vertex Cover
- DAA - Max Cliques
- Deterministic vs. Nondeterministic Computations
- DAA - Sublist Search
- DAA - Fibonacci Search
- DAA - Exponential Search
- DAA - Jump Search
- DAA - Interpolation Search
- DAA - Binary Search
- DAA - Linear Search
- Searching Techniques Introduction
- DAA - Radix Sort
- DAA - Counting Sort
- DAA - Bucket Sort
- DAA - Heap Sort
- DAA - Shell Sort
- DAA - Selection Sort
- DAA - Insertion Sort
- DAA - Bubble Sort
- DAA - Extract Method
- DAA - Heapify Method
- DAA - Insert Method
- DAA - Binary Heap
- Optimal Cost Binary Search Trees
- DAA - Multistage Graph
- DAA - Shortest Paths
- DAA - Spanning Tree
- Travelling Salesperson Approximation Algorithm
- Set Cover Problem
- Vertex Cover Problem
- Approximation Algorithms
- Fisher-Yates Shuffle
- Karger’s Minimum Cut
- Randomized Quick Sort
- Randomized Algorithms
- Travelling Salesman Problem | Dynamic Programming
- Longest Common Subsequence
- DAA - 0-1 Knapsack
- Floyd Warshall Algorithm
- Matrix Chain Multiplication
- DAA - Dynamic Programming
- DAA - Optimal Merge Pattern
- DAA - Job Sequencing with Deadline
- DAA - Fractional Knapsack
- Map Colouring Algorithm
- Dijkstra’s Shortest Path Algorithm
- Kruskal’s Minimal Spanning Tree
- Travelling Salesman Problem
- DAA - Greedy Method
- Towers of Hanoi
- Karatsuba Algorithm
- Strassen’s Matrix Multiplication
- DAA - Binary Search
- DAA - Merge Sort
- DAA - Max-Min Problem
- DAA - Divide & Conquer
- DAA - Space Complexities
- Master’s Theorem
- Time Complexity
- Asymptotic Notations & Apriori Analysis
- DAA - Methodology of Analysis
- DAA - Analysis of Algorithms
- DAA - Introduction
- Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
DAA - Heapify Method
Design and Analysis Heapify Method
Heapify method rearranges the elements of an array where the left and right sub-tree of ith element obeys the heap property.
Algorithm: Max-Heapify(numbers[], i) leftchild := numbers[2i] rightchild := numbers [2i + 1] if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] largest := leftchild else largest := i if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] largest := rightchild if largest ≠ i swap numbers[i] with numbers[largest] Max-Heapify(numbers, largest)
When the provided array does not obey the heap property, Heap is built based on the following algorithm Build-Max-Heap (numbers[]).
Algorithm: Build-Max-Heap(numbers[]) numbers[].size := numbers[].length fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 Max-Heapify (numbers[], i)Advertisements