作者:my76572 | 来源:互联网 | 2023-09-06 17:44
这里讲述的是用堆实现的最大优先级队列,建立的是最大堆,主要实现3个算法,一个是抽取对头元素,也就是整个堆里面最大的那个数,还有一个是提高某个节点的优先级,最后是往队尾插入元素。1、
这里讲述的是用堆实现的最大优先级队列,建立的是最大堆,主要实现3个算法,一个是抽取对头元素,也就是整个堆里面最大的那个数,还有一个是提高某个节点的优先级,最后是往队尾插入元素。
1、建立最大堆
void build_max_heap(int *a, int i, int n)
{
int max = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left a[max]) {
max = left;
}
if (right a[max]) {
max = right;
}
if (i != max) {
int temp = a[i];
a[i] = a[max];
a[max] = temp;
build_max_heap(a, max, n);
}
}
2、抽取对头元素
int extract_max(int *a, int n)
{
int max = a[0];
a[0] = a[n-1];
build_max_heap(a, 0, n-1);
return max;
}
3、将队列中的某个元素的优先级提高
int increase_key(int *a, int i, int key)
{
if (key return -1;
}
a[i] = key;
int p;
while (i > 0 && a[p=(i-1)/2]
int temp = a[p];
a[p] = a[i];
a[i] = temp;
i = p;
}
return 0;
}4、队尾插入元素
void heap_insert(int *a, int n, int key)
{
int i = n;
a[i] = key;
int p;
while (i > 0 && a[p=(i-1)/2]
int temp = a[p];
a[p] = a[i];
a[i] = temp;
i = p;
}
}
注意在插入的时候,要确保数组有足够的存储空间,n是当前数组元素的下一个位置
本文出自 “移动开发” 博客,请务必保留此出处http://ikinglai.blog.51cto.com/6220785/1384011
算法导论第6章代码之优先级队列,布布扣,bubuko.com