当前位置：首页 > news >正文

河南建设工程招标网站活动营销的方式有哪些

news 2025/6/30 22:40:03

河南建设工程招标网站,活动营销的方式有哪些,网站开发用什么软件有哪些,网站创建一般创建哪种类型1. 优先级队列概念： 队列是⼀种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，⼀般出队列时，可能需要优先级⾼的元素先出队列，所以， 数据结构应该提供两个最基本的操作&am…

1. 优先级队列

概念：

队列是⼀种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，⼀般出队列时，可能需要优先级⾼的元素先出队列，所以，数据结构应该提供两个最基本的操作，⼀个是返回最⾼优先级对象，⼀个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。JDK1.8中的PriorityQueue底层使⽤了堆这种数据结构。

2. 堆的概念

如果有⼀个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全⼆叉树的顺序存储⽅式存储在⼀个⼀维数组中，并满⾜： $k{_{i}}^{}<=k_{2i}^{}+1$ 且 $k{_{i}}^{}<=k_{2i}^{}+2$ 。

堆（Heap）是一种特殊的数据结构，通常用于实现 优先队列（Priority Queue）。堆是一种完全二叉树

3. 堆的性质

最大堆（Max Heap）：每个节点的值都大于或等于其子节点的值。根节点是堆中的最大值。
最小堆（Min Heap）：每个节点的值都小于或等于其子节点的值。根节点是堆中的最小值。

堆是一棵 完全二叉树，即除了最后一层，其他层都是满的，且最后一层的节点尽量靠左排列。
堆中任意节点的值总是满足堆的性质（最大堆或最小堆）。

4. 堆的存储方式

堆是使用数组以 层序遍历 的顺序存储的。

堆的数组存储是按照 层序遍历 的顺序依次存储完全二叉树的节点。对于数组中的任意一个节点 i：

左子节点 的索引为 2 * i + 1。
右子节点 的索引为 2 * i + 2。
父节点 的索引为 (i - 1) / 2。

5. 堆的创建

import java.util.Arrays;//小堆
public class PriorityQueue {public int[] elem;//创建数组，存储堆值public int size;//数组元素个数public int DATA_SIZE = 10;//无参构造方法public PriorityQueue(){elem = new int[DATA_SIZE];}//有参构造方法public PriorityQueue(int[] arr){elem = new int[arr.length];for(int i=0;i<arr.length;i++){elem[i] = arr[i];size++;}}//创建小堆public void createMinHeap(){for(int p = (size-1-1)/2;p>=0;p--){shiftDown(p);}}//向下调整public void shiftDown(int parent){// 如果数组为空或父节点索引无效，直接返回if(elem==null||parent<0){return;}// 左子节点的索引int child = 2*parent+1;while (child < size){// 找到较小的子节点if(child+1<size&&elem[child]>elem[child+1]){child = child +1;// 如果右子节点存在且更小，选择右子节点}// 如果子节点小于父节点，交换它们if(elem[child] < elem[parent]){swap(parent,child);parent = child;// 更新父节点索引child = 2*parent+1; // 更新子节点索引}else{//小堆存储，直接跳出循环break;}}}//交换元素public void swap(int i,int j){int n = elem[i];elem[i] = elem[j];elem[j] = n;}//添加元素public void offer(int val){//判满if(isFull()){//2倍扩容this.elem = Arrays.copyOf(elem,2*elem.length);}elem[size] = val;//插入元素到数组最后shiftUp(size);//向上调整size++;}//向上调整private void shiftUp(int child){while(child>=0){int parent = (child-1)/2;if(parent>=0&&elem[child]<elem[parent]){swap(child,parent);child = parent;}else {break;}}}//移除优先级最高元素public int poll(){if(isEmpty()){throw new NullPointerException("空指针异常");}int data = elem[0];//将头尾元素交换swap(0,size-1);size--;//向下调整shiftDown(0);return data;}//判满private boolean isFull(){return size ==elem.length;}//判空public boolean isEmpty(){return elem==null;}
}

2. 建堆的时间复杂度

1. 向下调整建堆

建堆的时间复杂度为O(N)

2. 向上调整建堆

向下调整与向上调整时间复杂度对比，选择向下调整的效率更高

3. 插入

1. 先将元素放⼊到底层空间中(注意：空间不够时需要扩容)

2. 将最后新插⼊的节点向上调整，直到满⾜堆的性质

向上调整（Heapify Up）：

时间复杂度：O(log n)。

4. 删除

注意：堆的删除⼀定删除的是堆顶元素。具体如下：

1. 将堆顶元素对堆中最后⼀个元素交换

2. 将堆中有效数据个数减少⼀个

3. 对堆顶元素进⾏向下调整

向下调整(以⼩堆为例)：

1. 让parent标记需要调整的节点，child标记parent的左孩⼦(注意：parent如果有孩⼦⼀定先是有左孩⼦)

2. 如果parent的左孩⼦存在，即:child < size，进⾏以下操作，直到parent的左孩⼦不存在

◦ parent右孩⼦是否存在，存在找到左右孩⼦中最⼩的孩⼦，让child进⾏标

◦ 将parent与较⼩的孩⼦child⽐较，如果：

▪ parent⼩于较⼩的孩⼦child，调整结束

▪ 否则：交换parent与较⼩的孩⼦child，交换完成之后，parent中⼤的元素向下移动，可能导致⼦树不满⾜对的性质，因此需要继续向下调整，即parent = child；child =parent*2+1; 然后继续2。

注意：在调整以parent为根的⼆叉树时，必须要满⾜parent的左⼦树和右⼦树已经是堆了才可以向下调整。

向下调整（Heapify Down）：

时间复杂度：O(log n)。

6. PriorityQueue接口

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。

1. PriorityQueue的使⽤注意

1. 使⽤时必须导⼊PriorityQueue所在的包
import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够⽐较⼤⼩，不能插⼊⽆法⽐较⼤⼩的对象，否则会抛出ClassCastException异常

3. 不能插⼊null对象，否则会抛出NullPointerException

4. 没有容量限制，可以插⼊任意多个元素，其内部可以⾃动扩容

5. 插⼊和删除元素的时间复杂度为

6. PriorityQueue底层使⽤了堆数据结构

7. PriorityQueue默认情况下是⼩堆---即每次获取到的元素都是最⼩的元素

2. 优先级队列的构造

        ArrayList<Integer> list = new ArrayList<>();list.add(10);list.add(30);list.add(15);list.add(14);⽤ArrayList对象来构造⼀个优先级队列的对象PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(list);priorityQueue.offer(12);

我们发现PriorityQueue默认情况下是⼩堆，如果需要⼤堆需要⽤⼾提供⽐较器

 ⽤⼾⾃⼰定义的⽐较器：直接实现Comparator接⼝，然后重写该接⼝中的compare⽅法即可
class IntCmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);//大堆}
}

    public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());priorityQueue.offer(10);priorityQueue.offer(30);priorityQueue.offer(15);priorityQueue.offer(14);priorityQueue.offer(12);}