Scribd
Upload
9 views2 pages

Heap

heap description

Uploaded by

Star Bawa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
9 views2 pages

Heap

heap description

Uploaded by

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

#include <iostream>

#include <conio.h>

using namespace std;

void swap(int &a, int &b)


{
int t;
t = a;
a = b;
b = t;
}

void heapify(int arr[], int n, int i)


{ //i=0 in first case
//find the largest root node ,left child and right child
int largest = i; //in first round we take largest as root

int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])


largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;

if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);

}
}
void heapsort(int arr[], int n)
{ //i=n/2-1 gives us the last node of the second last level
for (int i = n / 2 - 1; i >= 0; i--)
{
heapify(arr, n, i); //heapify will give the max heap of
//both the array
}

//heap sort deletion


for (int i = n - 1; i >= 0; i--)
{
swap(arr[0], arr[i]);

heapify(arr, i, 0);
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapsort(arr, n);

cout << "Sorted array is \n";


printArray(arr, n);
}

//O(nlog n) time complexity

You might also like