đây là bài số 5
#include
#define MAX 50
using namespace std;
struct Heap
{
int items[MAX];
int size;
int length;
};
int Parent(int i)
{
return (i - 1) / 2;
}
int Left(int i)
{
return 2*i + 1;
}
int Right(int i)
{
return 2*i + 2;
}
void Swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
void MaxHeapify(Heap *A, int i)
{
int l, r, largest;
l = Left(i);
r = Right(i);
if (l < A->size && A->items[l] > A->items[i])
largest = l;
else
largest = i;
if (r < A->size && A->items[r] > A->items[largest])
largest = r;
if (largest != i)
{
Swap(A->items[i], A->items[largest]);
MaxHeapify(A, largest);
}
}
void BuildMaxHeap(Heap *A)
{
A->size = A->length;
for(int i = A->length/2; i >= 0; i--)
MaxHeapify(A, i);
}
//copy array into heap
void Initialize(Heap *A, int arrInt[], int n)
{
A->length = n;
for (int i = 0; i < n; i++)
A->items[i] = arrInt[i];
}
void PrintArray(Heap *A)
{
for(int i = 0; i < A->length; i++)
cout << A->items[i] << " ";
cout << endl;
}
void PrintHeap(Heap *A)
{
for(int i = 0; i < A->size; i++)
cout << A->items[i] << " ";
cout << endl;
}
void Heapsort(Heap *A)
{
BuildMaxHeap(A);
for(int i = A->length - 1; i >= 1; i--)
{
Swap(A->items[0], A->items[i]);
A->size--;
MaxHeapify(A, 0);
}
}
int main()
{
Heap A;
int arrInt[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
int n = sizeof(arrInt)/sizeof(arrInt[0]);
Initialize(&A, arrInt, n);
cout << "Before sort:\n";
PrintArray(&A);
cout << "After sort:\n";
Heapsort(&A);
PrintArray(&A);
return 0;
}
Trang Chính
Fri May 22, 2015 5:20 pm
Tiêu đề: Các bài thực hành Cấu Trúc Dữ Liệu 
Prac 1.pdf 
