堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组对象。
对于具有 n 个结点的完全⼆叉树,如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号,则对于序号为 i 的结点有:
1. 若 i>0 , i 位置结点的双亲序号:(i - 1)/ 2;i 等于0时,i为根结点,没有双亲结点。
2. 若 2i+1 < n,左孩子序列: 2i+1, 2i+1>=n 否则⽆左孩⼦。
3. 若 2i+2 < n,右孩子序列: 2i+2, 2i+2>=n否则无右孩子
堆底层结构为数组,因此定义堆的结构为:
typedef int HPDataType;
typedef struct Heap
{
HPDataType* arr;
int size;
int capacity;
}HP;
//默认初始化堆
void HPInit(HP* php);
//堆的销毁
void HPDestroy(HP* php);
//堆的插⼊
void HPPush(HP* php, HPDataType x);
//堆的删除
void HPPop(HP* php);
//出堆数据
HPDataType HPTop(HP* php);
// 判空
bool HPEmpty(HP* php);
//交换
void swap(int* x, int* y);
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n);
//向上调整算法
void AdjustUp(HPDataType* arr, int child);
void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->capacity = php->size = 0;
}
void HPDestroy(HP* php)
{
assert(php);
if (php->arr)
free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
交换以及向上、向下调整算法
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//建大堆还是小堆将两个算法的第一个判断条件修改相反即可
//向上调整
void AdjustUp(HPDataType* arr,int child)
{
int parent = (child - 1) / 2;//根据子结点求父结点
while (child > 0)//直到子结点为根结点即循环停止
{
// >
if (arr[child] < arr[parent])//子结点小就交换,创建小堆
{
swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
//小堆:找左右孩子中找最小的
//大堆:找左右孩子中找大的
// <
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
// >
if (arr[child] < arr[parent]) //小堆,什么时候交换? 孩子比父亲小
{
swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HPPush(HP* php, HPDataType x)
{
assert(php);
//扩容
if (php->capacity == php->size)
{
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr[php->size] = x;
AdjustUp(php->arr, php->size);
++php->size;
}
void HPPop(HP* php)
{
assert(php && php->size);
swap(&php->arr[0], &php->arr[php->size - 1]);
--php->size;
AdjustDown(php->arr, 0, php->size);
}
// 判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//出堆数据
HPDataType HPTop(HP* php)
{
assert(php && php->size);
return php->arr[0];
}
堆排序是由堆这种数据结构所设计的一种排序算法
大根堆:每个父结点的值都大于子结点
小根堆 :每个父结点的值都小于子结点
在了解完堆之后,需要先了解建堆,建堆有向上建堆建大堆或者小堆,也有向下建堆建大堆或者小堆
建大堆还是小堆看子结点和父结点的比较关系是大于还是小于
新数据插⼊到数组的尾上,再进行向上调整算法,直到满⾜堆。
• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后 • 插⼊之后如果堆的性质遭到破坏,将新插⼊结点顺着其双双亲往上调整到合适位置即可
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//建大堆还是小堆将两个算法的第一个判断条件修改相反即可
//向上调整
void AdjustUp(HPDataType* arr,int child)
{
int parent = (child - 1) / 2;//根据子结点求父结点
while (child > 0)//直到子结点为根结点即循环停止
{
// >
if (arr[child] < arr[parent])//子结点小就交换,创建小堆
{
swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
第1层,2^0个结点,需要向上移动0层 第2层,2^1个结点,需要向上移动1层 第3层,2^2个结点,需要向上移动2层 第4层,2^3个结点,需要向上移动3层 .............................................................. 第h层,2^(h-1)个结点,需要向上移动h-1层
则需要移动结点总的移动步数为:每层结点个数 * 向上调整次数(第⼀层调整次数为0)
由此可得:
向上调整算法建堆时间复杂度为:O(n ∗ log2 n)
因为堆是完全⼆叉树,⽽满⼆叉树也是完全⼆叉树,此处为了简化使⽤满⼆叉树来证明(时间复杂度本 来看的就是近似值,多⼏个结点不影响最终结果)
堆的删除:
删除堆是删除堆顶的数据,将堆顶的数据根最后⼀个数据⼀换,然后删除数组最后⼀个数据,再进⾏向下调整算法。
• 将堆顶元素与堆中最后⼀个元素进⾏交换 • 删除堆中最后⼀个元素 • 将堆顶元素向下调整到满⾜堆特性为⽌
//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
//小堆:找左右孩子中找最小的
//大堆:找左右孩子中找大的
// <
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
// >
if (arr[child] < arr[parent]) //小堆,什么时候交换? 孩子比父亲小
{
swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HPPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
第1层,2^0个结点,需要向下移动h-1层 第2层,2^1个结点,需要向下移动h-2层 第3层,2^2个结点,需要向下移动h-3层 第4层,2^3个结点,需要向下移动h-4层 ...... 第h-1层,2^(h−2)个结点,需要向下移动1层
则需要移动结点总的移动步数为:每层结点个数 * 向下调整次数
向下调整算法建堆时间复杂度为:O(n)
//堆排序
void HeapSort(int* arr, int n)
{
//建堆
//升序——大堆
//降序——小堆
//向上调整算法建堆
//for (int i = 0; i < 6; i++)
//{
// AdjustUp(arr, i);
//}
//向下调整算法建堆
//for (int i = (n - 1- 1) / 2; i >= 0; i--)
//{
// AdjustDown(arr, i, n);
//}
//循环将堆顶数据和最后一个数据进行交换
int end = n - 1;
while (end > 0)
{
swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}
第1层,2^0个结点,交换到根结点后,需要向下 移动0层 第2层,2^1个结点,交换到根结点后,需要向下 移动1层 第3层,2^2个结点,交换到根结点后,需要向下 移动2层 第4层,2^3个结点,交换到根结点后,需要向下 移动3层 ...... 第h层,2^(h-1)个结点,交换到根结点后,需要向 下移动h-1层
通过分析发现,堆排序第⼆个循环中的向下调整与建堆中的向上调整算法时间复杂度计算⼀致,此处 不再赘述。因此,堆排序的时间复杂度为O(n + n ∗ log n) ,即(n log n)
选择排序的基本思想:每⼀次从待排序的数据元素中选出最小(或最大)的⼀个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
1. 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(小)的数据元素 2. 若它不是这组元素中的最后⼀个(第⼀个)元素,则将它与这组元素中的最后⼀个(第⼀个)元素交换 3. 在剩余的 array[i]--array[n-2](array[i+1]--array[n-1]) 集合中,重复上述步 骤,直到集合剩余1个元素
下面是直接选择排序的动态示意图
//方法一
void SelectSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int mini = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[mini])
{
mini = j;
}
}
Swap(&arr[i], &arr[mini]);
}
}
//方法二优化之后
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
++begin;
--end;
}
}
方法一类似于冒泡排序,所以运行效率相对来说很低。
直接选择排序的特性总结: 1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用。 2. 时间复杂度:O(N ^2) 。 3. 空间复杂度:O(1)。