Scribd
Upload
52 views

Design and Analysis of Algorithms 214.: Introduction To The C Programming Language

This document contains code and instructions for heap sort algorithms. It discusses reading a set of numbers into an array, and then using a max-heapify algorithm and a build-max-heap algorithm to sort the array and maintain the heap property. The max-heapify algorithm exchanges elements to ensure the root node is the largest. The build-max-heap algorithm calls max-heapify to build the heap from the array.

Uploaded by

Gamindu Udayanga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
52 views

Design and Analysis of Algorithms 214.: Introduction To The C Programming Language

This document contains code and instructions for heap sort algorithms. It discusses reading a set of numbers into an array, and then using a max-heapify algorithm and a build-max-heap algorithm to sort the array and maintain the heap property. The max-heapify algorithm exchanges elements to ensure the root node is the largest. The build-max-heap algorithm calls max-heapify to build the heap from the array.

Uploaded by

Gamindu Udayanga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 3

Design and Analysis of Algorithms 214.

Introduction to the C Programming Language.

Heap sort Algorithms.

U.U.Samantha Rajapaksha
B.Sc.(Eng.)

Sri Lanka Institute of Information Technology.


[email protected]
0112301904

DAA 214 Sri Lanka Institute of Information Technology.


Exercise 09.
 Write a program to read a set of numbers and store them on an array. Then
using the following psedocode for heapify algorithm maintain the heap property
for the root node.

MAX-HEAPIFY(A, i)

1 l ← LEFT(i)
2 r ← RIGHT(i)
3 if l ≤ heap-size[A] and A[l] > A[i]
4 then largest ← l
5 else largest ← i
6 if r ≤ heap-size[A] and A[r] > A[largest]
7 then largest ← r
8 if largest ≠ i
9 then exchange A[i] ↔ A[largest]
10 MAX-HEAPIFY(A, largest)

DAA 214 Lab 02 Sri Lanka Institute of Information Technology.


Exercise 10.
 Modify the previous program in exercise 09 with
Buildheap algorithm given below to build a heap.

BUILD-MAX-HEAP(A)
1 heap-size[A] ← length[A]
2 for i ← ⌊length[A]/2⌋ downto 1
3 do MAX-HEAPIFY(A, i)

DAA 214 Lab 02 Sri Lanka Institute of Information Technology.

You might also like