// 12:06 PM/09/28/2017
#pragma once
//向下调整算法 主要用来make_heap 以及pop_heap
inline void adjustDown(int* heap, const int first, const int last)
{
if (last == first + )return;
int value = heap[first];
int hole = first;//当前要调整的节点
int childHole = hole * ;//其左子女节点
while (childHole < last)//当左子女节点存
{
if (childHole < last - && heap[childHole] < heap[childHole + ])//如果左右子女都存在
childHole++;
if (value > heap[childHole]) break; {
//当待调整元素 比子女元素小是，将子女元素移动到父节点
heap[hole] = heap[childHole];
hole = childHole;//将该子女元素设置为洞
childHole = hole * ;
}
}
heap[hole] = value;
} //像上调整 实际上也就是 pop_heap
inline void adjustUp(int* heap, const int first, const int last)
{
if (last == first + )return;
int hole = last - ;//最后一个元素设置为洞
int parentHole = hole / ;//该元素的父节点
int value = heap[last - ];//当前要调整元素
while (parentHole >= first && value > heap[parentHole])//父节点存在，且当前值大于父节点
{
heap[hole] = heap[parentHole];//父节点的值给当前洞
hole = parentHole;//父节点设置为洞
parentHole = hole / ;
}
heap[hole] = value;
} inline void push_heap(int* heap, const int firstIndex, const int lastIndex)
{
adjustUp(heap, firstIndex, lastIndex);
} //弹出最大元素
inline void pop_head(int* heap, const int firstIndex, const int lastIndex)
{
int value = heap[firstIndex];//要弹出的元素
heap[firstIndex] = heap[lastIndex - ];//把最后一个元素给要弹出的
heap[lastIndex - ] = value;//要弹出的放到最后
adjustDown(heap, firstIndex, lastIndex - );//进行向下调整
} inline void sort_heap(int* heap, int firstIndex, int lastIndex)
{
int curLast = lastIndex;
while (curLast > firstIndex)
{
pop_head(heap, firstIndex, curLast);
curLast--;
}
} inline void make_heap(int* heap, int firstIndex, int lastIndex)
{
int hole = (lastIndex - ) / ;
while (hole >= firstIndex)
{
adjustDown(heap, hole, lastIndex);
hole--;
}
} inline void partial_sort(int* heap, const int first, const int middle, const int last)
{
int i = middle;
make_heap(heap, first, middle);
while (i < last)
{
if (heap[i] < heap[first])
{
int value = heap[first];
heap[first] = heap[i];
heap[i] = value;
adjustDown(heap, first, middle);
}
i++;
}
sort_heap(heap, first, middle);
}