堆

概念

image-20211012141012636

最大堆:最上面的结点数值最大

特点:
1.每个结点最多可以有两个结点

2.根结点的键值是所有结点中最大的，每个结点的值都比孩子的值大。

3.除了根节点没有兄弟结点，最后一个左子结点可以没有兄弟结点，其他结点必须有兄弟结点。(有这个限制，下面的求子结点和父结点的公式才能成立。)

最小堆:最上面的结点数值最小….其他同最大堆

堆是最有个性的树，用数组表示的树。

image-20211012142229662

在数组中快速创建堆

左图——》右图

image-20211012143038239

1.找到最后一个结点的父结点，(该父结点)与其子结点进行比较大小，若某个子结点大于父结点，则与该父结点交换位置。(就是从最后一个非叶子结点开始进行调整，(向下调整就是找到该父结结点的子结点，进行调整。))

2.再移动到前一个父结点，进行上述操作。

3……

补充:static修饰的全局函数

一个普通的全局的静态函数。. 这样的static函数与普通函数的区别是：用static修饰的函数，限定在本源码文件中，不能被本源码文件以外的代码文件调用。

链接——链接

相关接口实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
//堆的结构
typedef struct _Heap
{
	int* arr;
	int size;
	int capacity;
}Heap;


void buildHeap(Heap& hp);
void adjustDown(Heap& hp, int index);
bool insertHeap(Heap& hp, int val);

//堆的初始化
bool initHeap(Heap& hp, int* orginal, int size)
{
	int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;
	hp.arr = new int[capacity];
	if (!hp.arr)
	{
		return false;
	}
	hp.capacity = capacity;
	hp.size = 0;

	//如果存在原始数据则构建堆
	if (size > 0)
	{
		//方式1：直接全部拿过来
		/*_memccpy(hp.arr, orginal, size, size * sizeof(int));
		hp.size = size;
		buildHeap(hp);*/

		//方式2：一个一个插入 ，插一次排一次
		for (int i = 0; i < size; i++)
		{
			insertHeap(hp, orginal[i]);
		}
	}
	return true;
}

//构建堆
void buildHeap(Heap& hp)
{
	for (int i = ((hp.size - 1)-1) / 2; i >= 0; i--)
	{
		adjustDown(hp, i);
	}
}

//向下调整——根据已经有的数据内容进行调整
void adjustDown(Heap& hp,int index)
{
	int cur = hp.arr[index];//当前父节点的值
	int parent = 0;//索引
	int child = 0;
	//调整是一个循环的过程，整个向下
	//能够进入循环的条件，它得有左子结点。
	for (parent = index; (parent * 2 + 1) < hp.size; parent = child)//for循环的最后一个参数，定位新的父结点索引
	{
		//从最后一个父结点开始，父结点肯定有左孩子
		child = parent * 2 + 1;
		 
		//取两个子结点中较大的一个
		if (((child + 1) < hp.size) && hp.arr[child] < hp.arr[child + 1])
		{
			child++;//如果右边的孩子大，那就拿到右边孩子的下标
		}
	
		//将子结点与父结点进行对比
		if (cur >= hp.arr[child])
		{
			break;//如果在高层，此时父结点大于子结点就break,因为是从底层上来的，比父结点都大
		}
		else
		{
			hp.arr[parent] = hp.arr[child];
			hp.arr[child] = cur;
		}
	}
}

//向上调整——对新插入的元素进行调整
void adjustUp(Heap& hp, int index)
{
	while (index > 0)
	{
		int temp = hp.arr[index];//要插入的结点
		int parent = (index - 1) / 2;
		if (temp > hp.arr[parent])
		{
			hp.arr[index] = hp.arr[parent];
			hp.arr[parent] = temp;
			index = parent;
		}
		else
		{
			//如果已经小于等于父亲的值了
			break; 
		}
	}
}

//加入新的元素
bool insertHeap(Heap& hp, int val)
{
	if (hp.size == hp.capacity)
	{
		return false;
	}
	int index = hp.size;//保存新加入元素的位置，因为size要++
	hp.arr[hp.size++] = val;
	adjustUp(hp,index);
	return true;
}

//打印输出堆中元素
void printHeap(Heap& hp)
{
	int num = hp.size;
	int front = 0;
	int back = 1;
	int row = 1;
	while (num)
	{
		for (int j = front; j < back; j++)
		{
			cout << hp.arr[j] << " ";
		}
		cout << endl;
		num -= row;//输出完本行还剩的元素个数
		//如果减去本行输出的个数小于0
		if (num <= 0)
		{
			break;
		}
		row *= 2;//下一行要输出的元素个数

		front = back;//定位下一行的起点

		if (num - row <= 0)//如果当前的元素个数不够输出下一行的，直接定位下一行的back位置
		{
			back = hp.size;
		}
		else// 够则——手动定位结尾位置
		{
			back += row;
		}
	}

}

//弹出堆顶元素
void popTop(Heap& hp)
{
	hp.arr[0] = hp.arr[hp.size - 1];
	hp.size--;
	buildHeap(hp);

}

构建堆 and 向下调整的图解

image-20211012163121314

补充——打印输出

堆插入元素按升序(降序)排序的效率时很高的，因为只需要和父亲比较。父亲的父亲……

应用

构建优先队列

操作系统内核作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

image-20211013092337526

如果最小键值元素拥有最高的优先级，那么这种优先队列叫作升序优先队列（即总是先删除最小 的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作降序优先队列 （即总是先删除最大的元素）；由于这两种类型是完全对称的，所以只需要关注其中一种。

核心实现同上建最大堆，就是把其中的数据换成了Task(任务，里面包括优先级，等其他属性)，根据优先级的大小，来创建堆。

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特 点快速定位指定索引的元素。

选择排序工作原理:第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置， 然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

类似于上面构建最大堆时的弹出堆顶元素。只是不将最后一个元素删除(不size–)，而是不断的将建好的大堆堆顶元素放到最后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
using namespace std;

void adjustDown(int* ary, int index, int tatal)
{
	int cur = ary[index];
	int parent = 0;
	int child = 0;

	for (parent = index; (parent * 2 + 1) < tatal; parent = child)
	{
		child = parent * 2 + 1;
		if (((child + 1) < tatal) && (ary[child] < ary[child + 1]))
		{
			child++;
		}
		
		if (cur >= ary[child])
		{
			break;
		}
		else
		{
			ary[parent] = ary[child];
			ary[child] = cur;
		}
	}
}


void HeapSort(int* ary,int size)
{
	int tempS = size;
    //先用这个数组键一个堆
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		adjustDown(ary, i, tempS);
	}
    //必须要先建好一个堆
    //因为这样将堆顶元素和堆尾元素交换之后，除了堆顶新换过来了元素，“仍”是一个最大(小)堆，因为比较就要和父节点比。
    
	int front = 0;
	int back = tempS - 1;
	for (;back > 0; back--)
	{ 
		int tempChange = ary[front];
		ary[front] = ary[back];
		ary[back] = tempChange;
		adjustDown(ary, front, --tempS);
	}	
}

int main(void)
{
	int arraY[] = {3,1,2,4,56,7,89,99};
	int size = sizeof(arraY) / sizeof(arraY[0]);

	HeapSort(arraY, size);

	for (int i = 0; i < size; i++)
	{
		cout << arraY[i] << " ";
	}
	return 0;
}