堆(2)--最大优先级队列

xiaoxiao2021-02-28  20

1. 优先级队列

优先级队列是一种用来维护由一组元素构成的集合S的数据结构,这一组元素中的每一个都有一个关键字key。 一个最大优先级队列支持以下操作:         INSERT(S, x): 把元素x插入集合S。         MAXIMUM(S): 返回S中具有最大关键字的元素。         EXTRACT-MAX(S): 去掉并返回S中的具有最大关键字的元素。         INCREASE-KEY(S, x, k): 将元素x的关键字的值增加到k,这里k值不能小于x的原关键字的值。 最大优先级队列的一个应用是在一台分时计算机上进行作业调度。这种队列对要执行的各作业及它们之间的相对优先关系加以记录。当一个作业做完或者中断时,用EXTRACT-MAX操作从所有等待的作业中,选择出具有最高优先级的作业。在任何时候,一个新作业都可以用INSERT加入到队列中去。

2. 用最大堆实现最大优先级队列

#include<stdio.h> #include <limits.h> void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; } int parent(int i) { if (i == 0) return 0; return (i - 1) / 2; } int left(int i) { return 2 * i + 1; } int right(int i) { return 2 * i + 2; } void max_heapify(int a[], int n, int i) { int l = left(i); int r = right(i); int largest; if (l <= n && a[l] > a[i]) largest = l; else largest = i; if (r <= n && a[r] > a[largest]) largest = r; if (largest != i) { swap(&a[i], &a[largest]); max_heapify(a, n, largest); } } void build_max_heap(int a[], int n) { int heap_size = n; int i; for (i = heap_size / 2 - 0; i >= 0; i--) max_heapify(a, n, i); } int heap_maximum(int a[], int n) { return a[0]; } int heap_extract_max(int a[], int n) { int heap_size = n; if (heap_size < 1) return -1; int max = a[0]; a[0] = a[heap_size - 1]; heap_size--; max_heapify(a, heap_size, 0); return max; } int heap_increase_key(int a[], int n, int i, int key) { if (key < a[i]) return -1; a[i] = key; while (i > 0 && a[parent(i)] < a[i]) { swap(&a[i], &a[parent(i)]); i = parent(i); } return 0; } void max_heap_insert(int a[], int n, int key) { int heap_size = n + 1; a[heap_size - 1] = INT_MIN; heap_increase_key(a, heap_size, heap_size - 1, key); } int main(int argc, char * argv[]) { int a[10] = { 1,2,3,4,5,6,7,8,-1,-1 }; int i; build_max_heap(a, 8); printf("max-priority-queue:"); //num:8 for (i = 0; i < 10; i++) printf("%d ", a[i]); printf("\n"); int max = heap_maximum(a, 8); int max1 = heap_extract_max(a, 8); printf("MAXIMUM: %d\n", max); printf("EXTRACT-MAX: %d\n", max1); printf("after EXTRACT-MAX:"); //num:7 for (i = 0; i < 10; i++) printf("%d ", a[i]); printf("\n"); heap_increase_key(a, 8, 7, 10); printf("after INCREASE-KEY:"); //num:7 for (i = 0; i < 10; i++) printf("%d ", a[i]); printf("\n"); max_heap_insert(a, 7, 9); printf("after INSERT:"); //num:8 for (i = 0; i < 10; i++) printf("%d ", a[i]); printf("\n"); return 0; }
转载请注明原文地址: https://www.6miu.com/read-2250361.html

最新回复(0)