什么堆？
- 堆就是用数组实现的完全二叉树结构（除叶节点以外，所有节点都是非空，且叶节点从左到右排列）。
- 完全二叉树中如果每颗子树的的最大值都在顶部就是大根堆。
- 完全二叉树中如果每颗子树的的最小值都在顶部就是小根堆。
- 堆结构就是heapInsert与heapfy操作。
- 堆结构的增加和减少。
- 优先级队列就是堆结构。
堆的heapInsert与heapfy操作
数组：1 9 4 8 2 6
索引：0 1 2 3 4 5
对应的完全二叉树结构：
数组模拟完全二叉树
索引 i：i的左孩子对应的索引2*i+1
i的右孩子对应的索引2*i+2
i的父节点对应的索引(i-1)/2
- heapInsert操作
某个位置处在index位置上往上继续移动，自下而上，构建大根堆/小根堆---------heapinsert操作
#include
#include
using namespace std;
//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector&arr, int index)
{
int parent = (index - 1) / 2;
while (arr[index] > arr[parent])
{
swap(arr[index], arr[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
int main()
{
vectorarr = { 1,9,4,8,2,6 };
for (int i = 0; i < arr.size(); i++)
{
heapinsert(arr, i);
}
for (auto e : arr)
{
cout << e << " ";
}
return 0;
} 运行结果：
- heapfy操作
某个数在index位置，能否往下移动，自上而下，构建大根堆/小根堆---------heapfy操作
#include
#include
using namespace std;
//某个数在index位置，能否往下移动---------heapfy操作
void heapify(vector&arr, int index, int heapsize)
{
//左孩子下标
int left = 2 * index + 1;
//两个孩子中谁大，就把下标给largest
while (left < heapsize) //左孩子存在
{
int largest;
if ((left + 1 < heapsize arrleft 1> arr[left])
{
largest = left + 1;
}
else
{
largest = left;
}
if (arr[largest] > arr[index])
{
largest = largest;
}
else
{
largest = index;
}
if (largest == index)
{
break;
}
swap(arr[largest], arr[index]);
index = largest;
left = index * 2 + 1;
}
}
int main()
{
vectorarr = { 1,9,4,8,2,6 };
for (int i = arr.size()-1; i >= 0; i--)
{
heapify(arr, i, arr.size());
}
int len = arr.size();
for (auto e : arr)
{
cout << e << " ";
}
return 0;
} 运行结果：
堆排序
- 基本思想
用数组来模拟构建大根堆，完成数组的升序或降序。
- 堆排序算法代码
（1）升序----构建大根堆
#include
#include
using namespace std;
//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector&arr, int index)
{
while (arr[index] > arr[(index - 1) / 2])
{
swap(arr[index], arr[(index - 1) / 2]);
}
}
//某个数在index位置，能否往下移动---------heapfy操作
void heapify(vector&arr, int index, int heapsize)
{
//左孩子下标
int left = 2 * index + 1;
//两个孩子中谁大，就把下表给largest
while (left < heapsize) //左孩子存在
{
int largest;
if ((left + 1 < heapsize arrleft 1> arr[left])
{
largest = left + 1;
}
else
{
largest = left;
}
if (arr[largest] > arr[index])
{
largest = largest;
}
else
{
largest = index;
}
if (largest == index)
{
break;
}
swap(arr[largest], arr[index]);
index = largest;
left = index * 2 + 1;
}
}
//堆排序----升序
void heap_sort(vector&arr,int len)
{
if (len < 2) return;
//heapinsert构建大根堆
//for (int i = 0; i < len i heapinsertarr i heapfy forint i='len' - 1 i>=0; i--)
{
heapify(arr, i, len);
}
int heapsize = len;
swap(arr[0], arr[--heapsize]);
while (heapsize > 0)
{
heapify(arr, 0, heapsize);
swap(arr[0], arr[--heapsize]);
}
}
int main()
{
vectorarr = { 1,9,4,8,2,6 };
int len = arr.size();
heap_sort(arr, len);
for (auto e : arr)
{
cout << e << " ";
}
return 0;
} 运行结果：
（2）降序---构建小根堆
#include
using namespace std;
#include
//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector& arr, int index)
{
int parent = (index - 1) / 2;
while (arr[index] < arr[parent])
{
swap(arr[index], arr[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
//某个数在index位置，能否往下移动---------heapfy操作
void heapify(vector& arr, int index, int heapsize)
{
//左孩子下标
int left = 2 * index + 1;
//两个孩子中谁大，就把小标给small
while (left < heapsize) //左孩子存在
{
int small;
if ((left + 1 < heapsize) && arr[left + 1] < arr[left])
{
small = left + 1;
}
else
{
small = left;
}
if (arr[small] < arr[index])
{
small = small;
}
else
{
small = index;
}
if (small == index)
{
break;
}
swap(arr[small], arr[index]);
index = small;
left = index * 2 + 1;
}
}
//堆排序,降序
void heap_sort(vector& arr, int len)
{
if (len < 2) return;
//heapinsert构建小根堆
for (int i = 0; i < len i heapinsertarr i heapfy for int i='len' - 1 i>= 0; i--)
//{
// heapify(arr, i, len);
//}
int heapsize = len;
swap(arr[0], arr[--heapsize]);
while (heapsize > 0)
{
heapify(arr, 0, heapsize);
swap(arr[0], arr[--heapsize]);
}
}
int main()
{
vector arr = { 1,9,4,8,2,6 };
//for (int i = 0; i < arr.size i heapinsertarr i for int i='arr.size()' - 1 i>= 0; i--)
//{
// heapify(arr, i, arr.size());
//}
heap_sort(arr, arr.size());
for (int i = 0; i < arr.size(); i++)
{
cout << arr[i] << " ";
}
return 0;
} 运行结果：
算法特性
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定