Page 249 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Store 7 in the hole (as the only remaining element in the heap):

7 is the last element from the heap, so now the array is sorted:

The implementation of heap sort in C is shown below:
#include< iostream >
using namespace std;

void insert (int v[], int &N, int a)
{
v[N]=a;
N++;
int child=N-1;
int parent=abs((child-1)/2);
while(parent >=0)
{
if(v[child]>v[parent])
{
v[child]=v[parent]+v[child];
v[parent]=v[child]–v[parent];
v[child]=v[child]–v[parent];
child=parent;
parent=abs((child-1)/2);
}
else
parent=-1;
}
}int remove(int v[],int N)
{
int a=v[0];
v[0]=v[N-1];
N—;
int parent=0;
int child=1;
while(child<=N-1)
{

242 LOVELY PROFESSIONAL UNIVERSITY