- 堆就是用数组实现的完全二叉树结构（除叶节点以外，所有节点都是非空，且叶节点从左到右排列）。
- 完全二叉树中如果每颗子树的的最大值都在顶部就是大根堆。
- 完全二叉树中如果每颗子树的的最小值都在顶部就是小根堆。
- 堆结构就是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<iostream>
#include<vector>
using namespace std;
//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector<int>&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()
{
vector<int>arr = { 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<iostream>
#include<vector>
using namespace std;
//某个数在index位置，能否往下移动---------heapfy操作
void heapify(vector<int>&arr, int index, int heapsize)
{
//左孩子下标
int left = 2 * index 1;
//两个孩子中谁大，就把下标给largest
while (left < heapsize) //左孩子存在
{
int largest;
if ((left 1 < heapsize) && arr[left 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()
{
vector<int>arr = { 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<iostream>
#include<vector>
using namespace std;
//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector<int>&arr, int index)
{
while (arr[index] > arr[(index - 1) / 2])
{
swap(arr[index], arr[(index - 1) / 2]);
}
}
//某个数在index位置，能否往下移动---------heapfy操作
void heapify(vector<int>&arr, int index, int heapsize)
{
//左孩子下标
int left = 2 * index 1;
//两个孩子中谁大，就把下表给largest
while (left < heapsize) //左孩子存在
{
int largest;
if ((left 1 < heapsize) && arr[left 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<int>&arr,int len)
{
if (len < 2) return;
//heapinsert构建大根堆
//for (int i = 0; i < len; i )
//{
// heapinsert(arr, 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<int>arr = { 1,9,4,8,2,6 };
int len = arr.size();
heap_sort(arr, len);
for (auto e : arr)
{
cout << e << " ";
}
return 0;
}
运行结果：
（2）降序---构建小根堆
#include<iostream>
using namespace std;
#include<vector>
//堆操作--------heapinsert 和 heapfy
//某个位置处在index位置上 往上继续移动---------heapinsert操作
void heapinsert(vector<int>& 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<int>& 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<int>& arr, int len)
{
if (len < 2) return;
//heapinsert构建小根堆
for (int i = 0; i < len; i )
{
heapinsert(arr, 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<int> arr = { 1,9,4,8,2,6 };
//for (int i = 0; i < arr.size(); i )
//{
// heapinsert(arr, 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)
稳定性：不稳定
