heap data structure
时间:2010-09-12 来源:eholy
// Begin from a[1]
void MaxHeapify(int *a, int index, int len)
{
int l = index * 2;
int r = index * 2 + 1;
int largest = -1;
if (l <= len && a[l] > a[index])
{
largest = l;
}
else
{
largest = index;
}
if (r <= len && a[r] > a[largest])
{
largest = r;
}
if (largest != index)
{
int tmp = a[largest];
a[largest] = a[index];
a[index] = tmp;
MaxHeapify(a, largest, len);
}
}
void BuildMaxHeap(int *a, int len)
{
for (int i = len / 2; i > 0; i--)
{
MaxHeapify(a, i, len);
}
}
void MaxHeapify(int *a, int index, int len)
{
int l = index * 2;
int r = index * 2 + 1;
int largest = -1;
if (l <= len && a[l] > a[index])
{
largest = l;
}
else
{
largest = index;
}
if (r <= len && a[r] > a[largest])
{
largest = r;
}
if (largest != index)
{
int tmp = a[largest];
a[largest] = a[index];
a[index] = tmp;
MaxHeapify(a, largest, len);
}
}
void BuildMaxHeap(int *a, int len)
{
for (int i = len / 2; i > 0; i--)
{
MaxHeapify(a, i, len);
}
}
相关阅读 更多 +
排行榜 更多 +