2017-09-11 15:36:08 qq_39396275 阅读数 446
  • 数据结构与算法(C/C++实现)视频教程

    C/C++实现数据结构与算法视频培训课程全面介绍计算机行业,基本的数据结构与算法,既有理论的深度也有实战的技法。课程全程讲师手敲代码,一步步代你走进数据结构与算法。 本课程涉及的数据结构与算法有,栈,队列,单向链表,双向循环链表,树,二叉树,搜索二叉树,平衡搜索二叉树,冒泡,选择,直插,希尔,,归并等,课程还涉及深度优先算法与广度优先算法等等。

    3633 人正在学习 去看看 王桂林

优先队列的类定义

优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3)
删除.在最小优先队列(min priority
queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority
queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.

面试题:

优先队列通常采用(1)的数据结构实现,向队列中插入1个元素的时间复杂度为(2)

ans:
1.堆
2.O(logN)

解析:优先队列是一种常用的数据结构,通常用堆实现,也可以用其他方式实现。
对应于大顶堆和小顶堆,存在最大优先队列和最小优先队列。以最大优先队列为例,优先队列除了具有堆上的一些操作,如调整堆, 构建堆之外,还有获得优先队列的最大元素,抽取出优先队列的最大元素,向优先队列中插入一个元素和增大优先队列中某个元素的值。
其中除了获得优先队列的最大元素的时间复杂度是O(1)之外,其他操作均为二叉树的高度O(lgN)

详细请见:http://blog.csdn.net/changyuanchn/article/details/14564403#comments

2019-02-17 12:01:33 Sensente 阅读数 95
  • 数据结构与算法(C/C++实现)视频教程

    C/C++实现数据结构与算法视频培训课程全面介绍计算机行业,基本的数据结构与算法,既有理论的深度也有实战的技法。课程全程讲师手敲代码,一步步代你走进数据结构与算法。 本课程涉及的数据结构与算法有,栈,队列,单向链表,双向循环链表,树,二叉树,搜索二叉树,平衡搜索二叉树,冒泡,选择,直插,希尔,,归并等,课程还涉及深度优先算法与广度优先算法等等。

    3633 人正在学习 去看看 王桂林

形象化描述:可以插队的队列。

头文件:<queue>

定义方法:较为简单的常见优先队列可直接定义;

如:priority_queue<int,vector<int>,greater<int> >pq;

即定义一个越小的整数优先级越大的优先队列。

若想实现自定义排序,需重载运算符()

如:

struct cmp {
    bool operator() (const int a,const int b) const true{
                return a%10 > b%10; //即个位数大的优先级高
        }
    };

定义方法:priority_queue<int,vector<int>,cmp> pq;

注意:优先队列使用top()获得队首元素。

常用操作速览:

q.size();//返回q里元素个数
q.empty();//返回q是否为空,空则返回1,否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
q.back();//返回q的末尾元素

请注意:

priority_queue <node> q;
//node是一个结构体
//结构体里重载了‘<’小于符号
priority_queue <int,vector<int>,greater<int> > q;
//不需要#include<vector>头文件
//注意后面两个“>”不要写在一起,“>>”是右移运算符
priority_queue <int,vector<int>,less<int> >q;

例题:丑数(Uva 136)P120

形如:1,2,3,4,5,6,8,9,10,12,15等不能被除2,3,5以外的数整除的数,求第1500个丑数。

代码:

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int coeff[3]={2,3,5};

int main() {
    priority_queue<ll,vector<ll>,greater<ll> > pq;
    set<ll>s;
    pq.push(1);
    s.insert(1);
    for(int i=1;;i++) {
        ll x =pq.top();
        pq.pop();
        if(i==1500) {
            cout<<x<<endl;
            break;
        }
        for(int j=0;j<3;j++) {
            ll x2=x*coeff[j];//依次生成丑数
            if(!s.count(x2)) {//除重
                s.insert(x2);
                pq.push(x2);
            }
        }
    }
}

 

2015-12-19 15:56:20 tuke_tuke 阅读数 4564
  • 数据结构与算法(C/C++实现)视频教程

    C/C++实现数据结构与算法视频培训课程全面介绍计算机行业,基本的数据结构与算法,既有理论的深度也有实战的技法。课程全程讲师手敲代码,一步步代你走进数据结构与算法。 本课程涉及的数据结构与算法有,栈,队列,单向链表,双向循环链表,树,二叉树,搜索二叉树,平衡搜索二叉树,冒泡,选择,直插,希尔,,归并等,课程还涉及深度优先算法与广度优先算法等等。

    3633 人正在学习 去看看 王桂林

队列的特点是先进先出。通常都把队列比喻成排队买东西,大家都很守秩序,先排队的人就先买东西。但是优先队列有所不同,它不遵循先进先出的规则,而是根据队列中元素的优先权,优先权最大的先被取出。这就很像堆的特征:总是移除优先级最高的根节点。

重点:优先级队列,是要看优先级的,谁的优先级更高,谁就先得到权限。不分排队的顺序!

上篇文章解释了堆的概念实现,现在用堆实现优先队列:


//最大堆
import java.util.ArrayList;
public class Heap<E extends Comparable>{
	private ArrayList<E> list=new ArrayList<E>();//用数组实现堆
	
    public Heap(){}
    public Heap(E[] objects){
    	for(int i=0;i<objects.length;i++){
    		add(objects[i]);
    	}
    }
    
    public void add(E newObject){//添加一个元素
    	list.add(newObject);
    	int currentIndex=list.size()-1;
    	
    	while(currentIndex>0){
    		int parentIndex=(currentIndex-1)/2;//找到该结点的父结点
    		if(list.get(currentIndex).compareTo(list.get(parentIndex))>0){//与父节点比较
    			//如果当前结点的值大于父结点就交换位置
    			E temp=list.get(currentIndex);
    			list.set(currentIndex, list.get(parentIndex));
    			list.set(parentIndex, temp);   			
    		}
    		else
    			break;
    		currentIndex=parentIndex;
    	}    	
    }
    
    public E remove(){//删除并返回根结点,堆的特点是移除了根结点后还是堆
    	if(list.size()==0) return null;
    	
    	E removeObject=list.get(0);
    	list.set(0, list.get(list.size()-1));//把最后一个结点放在根结点的位置
    	list.remove(list.size()-1);
    	
    	int currentIndex=0;
    	while(currentIndex<list.size()){
    		int leftChildIndex=2*currentIndex+1;
    		int rightChildIndex=2*currentIndex+2;//左右孩子结点的坐标
    		
    		if(leftChildIndex>=list.size())break;
    		//比较左右孩子的值,使maxIndex指向值大的结点
    		 int maxIndex=leftChildIndex;
    		 if(rightChildIndex<list.size()){
    			 if(list.get(maxIndex).compareTo(list.get(rightChildIndex))<0){
    				 maxIndex=rightChildIndex;
    			 }
    		 }
    		 //如果当前结点的值小于其左右孩子中的大的值,就交换两个结点
    		 if(list.get(currentIndex).compareTo(list.get(maxIndex))<0){
    	          E temp=list.get(maxIndex);
    	          list.set(maxIndex, list.get(currentIndex));
    	          list.set(currentIndex, temp);
    	          currentIndex=maxIndex;
    	    	}
    		 else
    			 break;
    	}
    	
    	return removeObject;   	
    	
    }
    
    public int getSize(){
    	return list.size();
    }
    
}
MyPriorityQueue.java

public class MyPriorityQueue<E extends Comparable> {
       private Heap<E> heap=new Heap<E>();//用堆实现优先队列
     //入队列
       public void enqueue(E e){
       	heap.add(e); //这个add以后,堆会自己调整成一个新堆
       }
       //出队列
       public E dequeue(){
       	return heap.remove();//这移除出之后,堆会自己调整,还是一个新堆
       }
       public int getSize(){
       	return heap.getSize();
       }
      
}
TestMyPriorityQueueMainClass.java

public class TestMyPriorityQueueMainClass {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Patient p1=new Patient("John",2);
        Patient p2=new Patient("Tom",9);
        Patient p3=new Patient("Jack",4);
        Patient p4=new Patient("Michael",6);
        
        MyPriorityQueue<Patient> priorityQueue=new MyPriorityQueue<>();
        priorityQueue.enqueue(p1);
        priorityQueue.enqueue(p2);
        priorityQueue.enqueue(p3);
        priorityQueue.enqueue(p4);
        
        while(priorityQueue.getSize()>0){
        	System.out.print(priorityQueue.dequeue()+"  ");
        }
	}
    static class Patient implements Comparable{
         private String name;
         private int priority;
         public Patient(String name,int priority){
        	 this.name=name;
        	 this.priority=priority;
         }
         public String toString(){
        	 return name+"(priority:"+priority+")";
         }
		@Override
		public int compareTo(Object oo) {//比较优先级
			// TODO Auto-generated method stub			
			return this.priority-((Patient)oo).priority;
		}
    	
    }
}

测试结果:优先级高的先输出,优先级最高的就是堆的根节点








2016-11-29 20:04:57 burning1996 阅读数 615
  • 数据结构与算法(C/C++实现)视频教程

    C/C++实现数据结构与算法视频培训课程全面介绍计算机行业,基本的数据结构与算法,既有理论的深度也有实战的技法。课程全程讲师手敲代码,一步步代你走进数据结构与算法。 本课程涉及的数据结构与算法有,栈,队列,单向链表,双向循环链表,树,二叉树,搜索二叉树,平衡搜索二叉树,冒泡,选择,直插,希尔,,归并等,课程还涉及深度优先算法与广度优先算法等等。

    3633 人正在学习 去看看 王桂林

优先队列:优先队列是允许至少下列两种操作的数据结构:Insert(插入)和 DeleteMin(删除最小者)

我们使用二叉堆来实现优先队列

堆的性质堆是一颗完全二叉树只有最下面的两层结点度能够小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树),完全二叉树可以用数组表示,对于数组中任一为位置i上的元素,其左儿子在位置2i 上,右儿子在(2i + 1)上

堆序性质在一个堆中,对于每个节点X, X的父亲中的关键字小于(或等于)X中的关键字,根节点除外(它没有父亲节点)

#include <stdio.h>
#include <stdlib.h>
#define Mindata (-32767)
typedef struct HeapStruct{
	int Size;
	int Capacity;
	int *Elements; 
}*PriorityQueue, HeapStruct;

PriorityQueue Initialize(int MaxElements){//初始化列队,利用及结构体构建一个最多元素为MaxElements的二叉堆 
	PriorityQueue H;
	H = (PriorityQueue )malloc(sizeof(HeapStruct));
	H -> Elements = (int *)malloc((MaxElements + 1) * sizeof(int));
	H -> Size = 0;
	H -> Capacity  =  MaxElements;
	H -> Elements[0] = Mindata;
	return H;
}
void Insert(PriorityQueue H, int X){//向二叉堆里面插入元素 
	int i;
	for(i = ++H -> Size; H -> Elements[i / 2] > X; i /= 2){
		H -> Elements[i] = H -> Elements[i / 2];
	}
	H -> Elements[i] = X;
}
int DeleteMin(PriorityQueue H){//删除最小节点,即根节点 
	int i, child, LastElement, MinElement;
	MinElement = H -> Elements[1];
	LastElement = H -> Elements[H -> Size--];
	for( i = 1; 2 * i <= H -> Size; i = child){
		child = 2 * i;
		if(child != H -> Size && H -> Elements[child] > H -> Elements[child + 1]){
			child++;
		}
		if(LastElement > H -> Elements[child]){
			H -> Elements[i] = H -> Elements[child];
		}
		else 
		    break;
	}
	H -> Elements[i] = LastElement;
	return MinElement; 
}
int main(){
	int Array[] =  { 32, 21, 16, 24, 31, 19, 68, 65, 26, 13 };
	PriorityQueue H;
	H = Initialize(50);
	int i;
	for( i = 0; i < 10; i++){
		Insert(H, Array[i]);
	}
	for(i = 0; i < 10; i++){
		printf("%d ", DeleteMin(H));
	}
	return 0;
} 


2018-09-10 08:58:07 liu_jiachen 阅读数 236
  • 数据结构与算法(C/C++实现)视频教程

    C/C++实现数据结构与算法视频培训课程全面介绍计算机行业,基本的数据结构与算法,既有理论的深度也有实战的技法。课程全程讲师手敲代码,一步步代你走进数据结构与算法。 本课程涉及的数据结构与算法有,栈,队列,单向链表,双向循环链表,树,二叉树,搜索二叉树,平衡搜索二叉树,冒泡,选择,直插,希尔,,归并等,课程还涉及深度优先算法与广度优先算法等等。

    3633 人正在学习 去看看 王桂林

说到队列,简单来理解就是排队嘛。排在最前面的肯定最先处理。
先不说在数据结构与算法中的优先队列,在现实生活中,比如说我们排队取车票的时候,“不好意思,我的车马上到点了,先让我取一下”如此情况屡见不鲜。
这就叫做优先队列。

实现思路

方法一:设置优先级,然后在正确的位置添加元素;
方法二:用入列操作添加元素,然后按照优先级处理。

Talk is Cheap , Show Me the Code

/*
*Author : ljccccccccccc@163.com
*/
function priorityQueue() {
    let items = [];
    function QueueElement(element, priority) {
        this.element = element;
        this.priority = priority;
    }

    this.enqueue = function (element, priority) {
        let queueElement = new QueueElement(element, priority);

        let added = false;
        for (let i = 0; i < items.length; i++) {
            if (queueElement.priority < items[i].priority) {
                items.splice(i, 0, queueElement);
                added = true;
                break;
            }
        }
        if (!added) {
            items.push(queueElement);
        }
    }
    this.print = function () {
        for(let i = 0; i < items.length; i ++){
        //两种方法输出都可以
            // console.log(`${items[i].element} - ${items[i].priority}`);
            console.log(items[i].element +"  -  "+items[i].priority);
        }
    }
    //其他实现与队列相同
        //删除
        this.dequeue = function (el) {
            return items.shift();
        }
        //查看队列头元素
        this.front = function () {
            return items[0];
        }
        //检查是否为空
        this.isEmpty = function () {
            return items.length === 0;
        }

}

let pri = new priorityQueue();

pri.enqueue('Hilleny',1);
pri.enqueue('Funny',3);
pri.enqueue('Hilleny',1);
pri.enqueue('Hilleny',1);
pri.enqueue('Hilleny',1);
pri.enqueue('Jhon',2);
pri.enqueue('Hilleny',1);
pri.print();

第一个添加的Hilleny优先级为1,是队列中第一个元素,后面的Funny优先级为3,是第二个元素。当添加到第三个元素时,它的优先级为1,所以插入到优先级为3的前面。后同。当遇到优先级为2的Jhon时,splice(i ,0,Jhon),把Jhon插入到优先级为3的前面。
这就是优先队列。
看一下输出结果,再回味一下代码吧!

//结果输出
Hilleny  -  1
Hilleny  -  1
Hilleny  -  1
Hilleny  -  1
Hilleny  -  1
Jhon  -  2
Funny  -  3

这就是优先队列的实现。其中涉及到队列的知识,请前往
【JavaScript】JS数据结构与算法之队列

挚谢阅读。
wx:jc_960823 注明来意
163 : ljccccccccccc@163.com

链表实现优先队列

博文 来自: oChangWen
没有更多推荐了,返回首页