85 lines
1.5 KiB
C++
85 lines
1.5 KiB
C++
#pragma once
|
|
namespace ZZ_MATH
|
|
{
|
|
|
|
template<typename T>
|
|
void MinHeapify(T*arry, int size, int element)
|
|
{
|
|
int lchild = element * 2 + 1, rchild = lchild + 1;
|
|
while (rchild < size)
|
|
{
|
|
if (arry[element] <= arry[lchild] && arry[element] <= arry[rchild])
|
|
{
|
|
return;
|
|
}
|
|
if (arry[lchild] <= arry[rchild])
|
|
{
|
|
std::swap(arry[element], arry[lchild]);
|
|
element = lchild;
|
|
}
|
|
else
|
|
{
|
|
std::swap(arry[element], arry[rchild]);
|
|
element = rchild;
|
|
}
|
|
lchild = element * 2 + 1;
|
|
rchild = lchild + 1;
|
|
}
|
|
if (lchild < size&&arry[lchild] < arry[element])
|
|
{
|
|
std::swap(arry[lchild], arry[element]);
|
|
}
|
|
return;
|
|
}
|
|
|
|
template<typename T>
|
|
void MaxHeapify(T*arry, int size, int element)
|
|
{
|
|
int lchild = element * 2 + 1, rchild = lchild + 1;
|
|
while (rchild < size)
|
|
{
|
|
if (arry[element] >= arry[lchild] && arry[element] >= arry[rchild])
|
|
{
|
|
return;
|
|
}
|
|
if (arry[lchild] >= arry[rchild])
|
|
{
|
|
std::swap(arry[element], arry[lchild]);
|
|
element = lchild;
|
|
}
|
|
else
|
|
{
|
|
std::swap(arry[element], arry[rchild]);
|
|
element = rchild;
|
|
}
|
|
lchild = element * 2 + 1;
|
|
rchild = lchild + 1;
|
|
}
|
|
if (lchild<size&&arry[lchild]>arry[element])
|
|
{
|
|
std::swap(arry[lchild], arry[element]);
|
|
}
|
|
return;
|
|
}
|
|
|
|
|
|
template<typename T>
|
|
void HeapSort(T*arry, int size)
|
|
{
|
|
int i;
|
|
for (i = size - 1; i >= 0; i--)
|
|
{
|
|
MinHeapify(arry, size, i);
|
|
}
|
|
while (size > 0)
|
|
{
|
|
std::swap(arry[size - 1], arry[0]);
|
|
|
|
size--;
|
|
MinHeapify(arry, size, 0);
|
|
}
|
|
return;
|
|
}
|
|
|
|
}
|