盘县 网站建设成都高端模板建站

盘县 网站建设,成都高端模板建站,长沙做网站优化的公司,自己的卡盟网站怎么做分站一、优先队列概念优先队列是一种特殊的队列#xff0c;元素出队顺序不是FIFO#xff0c;而是按照优先级#xff1a;每次出队的是优先级最高#xff08;或最低#xff09;的元素二、两种实现方式对比特性使用数组/链表#xff08;朴素实现#xff09;使用堆#xff08;推…一、优先队列概念优先队列是一种特殊的队列元素出队顺序不是FIFO而是按照优先级每次出队的是优先级最高或最低的元素二、两种实现方式对比特性使用数组/链表朴素实现使用堆推荐实现入队时间复杂度O(1)O(log n)出队获取最高优先级时间复杂度O(n)O(log n)查找最高优先级O(n)O(1)三、数组实现1. 数组无序实现#include stdio.h #include stdlib.h #include limits.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int size; } PriorityQueueArray; // 初始化 void initPriorityQueueArray(PriorityQueueArray* pq) { pq-size 0; } // 入队 O(1) - 直接添加到尾部 void enqueueArray(PriorityQueueArray* pq, int value) { if (pq-size MAX_SIZE) { printf(队列已满\n); return; } pq-data[pq-size] value; } // 出队 O(n) - 需要遍历找到最大值 int dequeueArray(PriorityQueueArray* pq) { if (pq-size 0) { printf(队列为空\n); return INT_MIN; } // 找到最大值的索引 int maxIndex 0; for (int i 1; i pq-size; i) { if (pq-data[i] pq-data[maxIndex]) { maxIndex i; } } // 保存最大值 int maxValue pq-data[maxIndex]; // 用最后一个元素填补空缺 pq-data[maxIndex] pq-data[pq-size - 1]; pq-size--; return maxValue; } // 查看最高优先级 O(n) int peekArray(PriorityQueueArray* pq) { if (pq-size 0) return INT_MIN; int maxValue pq-data[0]; for (int i 1; i pq-size; i) { if (pq-data[i] maxValue) { maxValue pq-data[i]; } } return maxValue; } 2. 数组有序四、堆实现堆是一种特殊的完全二叉树满足最大堆父节点 ≥ 子节点最小堆父节点 ≤ 子节点1. 最大堆实现优先队列#include stdio.h #include stdlib.h #include limits.h #define MAX_HEAP_SIZE 100 typedef struct { int data[MAX_HEAP_SIZE]; int size; } MaxHeap; // 辅助函数交换两个元素 void swap(int* a, int* b) { int temp *a; *a *b; *b temp; } // 初始化堆 void initMaxHeap(MaxHeap* heap) { heap-size 0; } // 获取父节点索引 int parent(int i) { return (i - 1) / 2; } // 获取左孩子索引 int leftChild(int i) { return 2 * i 1; } // 获取右孩子索引 int rightChild(int i) { return 2 * i 2; } // 上浮操作维护堆性质O(log n) void heapifyUp(MaxHeap* heap, int index) { while (index 0 heap-data[parent(index)] heap-data[index]) { swap(heap-data[parent(index)], heap-data[index]); index parent(index); } } // 下沉操作维护堆性质O(log n) void heapifyDown(MaxHeap* heap, int index) { int maxIndex index; int left leftChild(index); int right rightChild(index); // 找到当前节点、左孩子、右孩子中的最大值 if (left heap-size heap-data[left] heap-data[maxIndex]) { maxIndex left; } if (right heap-size heap-data[right] heap-data[maxIndex]) { maxIndex right; } // 如果当前节点不是最大值交换并继续下沉 if (index ! maxIndex) { swap(heap-data[index], heap-data[maxIndex]); heapifyDown(heap, maxIndex); } } // 入队操作 O(log n) void heapEnqueue(MaxHeap* heap, int value) { if (heap-size MAX_HEAP_SIZE) { printf(堆已满\n); return; } // 1. 将新元素放到末尾 heap-data[heap-size] value; heap-size; // 2. 上浮调整 heapifyUp(heap, heap-size - 1); } // 出队操作 O(log n) int heapDequeue(MaxHeap* heap) { if (heap-size 0) { printf(堆为空\n); return INT_MIN; } // 1. 保存堆顶最大值 int maxValue heap-data[0]; // 2. 用最后一个元素替换堆顶 heap-data[0] heap-data[heap-size - 1]; heap-size--; // 3. 下沉调整 heapifyDown(heap, 0); return maxValue; } // 查看堆顶元素 O(1) int heapPeek(MaxHeap* heap) { if (heap-size 0) return INT_MIN; return heap-data[0]; } // 构建堆 O(n) - 弗洛伊德建堆法 void buildHeap(MaxHeap* heap, int arr[], int n) { // 复制数据 for (int i 0; i n; i) { heap-data[i] arr[i]; } heap-size n; // 从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; i--) { heapifyDown(heap, i); } } // 打印堆树状结构 void printHeapTree(MaxHeap* heap, int index, int level) { if (index heap-size) return; // 先打印右子树 printHeapTree(heap, rightChild(index), level 1); // 打印当前节点 for (int i 0; i level; i) printf( ); printf(%d\n, heap-data[index]); // 打印左子树 printHeapTree(heap, leftChild(index), level 1); }2. 最小堆实现typedef struct { int data[MAX_HEAP_SIZE]; int size; } MinHeap; // 最小堆的上浮操作 void minHeapifyUp(MinHeap* heap, int index) { while (index 0 heap-data[parent(index)] heap-data[index]) { swap(heap-data[parent(index)], heap-data[index]); index parent(index); } } // 最小堆的下沉操作 void minHeapifyDown(MinHeap* heap, int index) { int minIndex index; int left leftChild(index); int right rightChild(index); if (left heap-size heap-data[left] heap-data[minIndex]) { minIndex left; } if (right heap-size heap-data[right] heap-data[minIndex]) { minIndex right; } if (index ! minIndex) { swap(heap-data[index], heap-data[minIndex]); minHeapifyDown(heap, minIndex); } }五、时间复杂度对比分析各种实现的时间复杂度操作无序数组/链表有序数组堆插入(入队)O(1)O(n)O(log n)删除最大(出队)O(n)O(1)O(log n)获取最大(查看)O(n)O(1)O(1)构建O(1)O(n log n)O(n)