堆排序是一種常見的排序算法，其時間復雜度為O(logN)，重要思想為建堆取極值，根據需求進行排序，如下圖：
值得思考的是，二次建堆的過程中，實際上是沒有必要將所有元素都進行下調，只需要將根進行下調：
實現代碼如下：
template <class T>//建立仿函數模板滿足排序需求
struct CompMax
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
template <class T>
struct CompMin
{
bool operator()(const T& a,const T& b)
{
return a < b;
}
};
template <class T ,class Com = CompMax<T> >
static void HeapSort(vector<T>&list)
{
size_t size = list.size();
GetHeap<T>(list, size);
swap(list[0], list[size - 1]);
while (--size > 1)
{
adjustdown<T>(0, size, list);
swap(list[0], list[size - 1]);
}
}
template <class T,class Com = CompMax<T> >
void adjustdown(int index, size_t size, vector<T>&list)
{
Com comp;
size_t parent = index;
size_t child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size)
child = child = comp(list[child], list[child + 1]) ? child : child + 1;
if (!comp(list[parent], list[child]))
{
std::swap(list[child], list[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
template <class T ,class Com = CompMax<T> >
static void GetHeap(vector<int>&list, size_t size)
{
size_t parent = (size - 2) / 2;
int begin = parent;
Com comp;
while (begin >= 0)
{
size_t child = parent * 2 + 1;
while (child<size)
{
if (child + 1<size)
child = child = comp(list[child], list[child + 1]) ? child : child + 1;
if (!comp(list[parent], list[child]))
{
swap(list[child], list[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
parent = --begin;
}
} 如有不足，希望指正，有疑問也希望提出
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
