精华内容
下载资源
问答
  • 顶堆/小顶堆

    2020-11-19 19:32:40
    小顶堆 小顶堆是堆顶元素最小(控制堆中元素个数,比堆顶元素大的元素才能入堆,可以用来确定第k大的数) class MinHeap{ private int capacity; private int count; private int[] elements; public MinHeap...

    小顶堆

    小顶堆是堆顶元素最小(控制堆中元素个数,比堆顶元素大的元素才能入堆,可以用来确定第k大的数)

    class MinHeap{
        private int capacity;
        private int count;
        private int[] elements;
    
        public MinHeap(int capacity) {
            this.capacity = capacity;
            elements = new int[capacity];
        }
    
        public void insert(int num) {
            if (count >= capacity) return;
            elements[count] = num; // 新加入的元素放堆底部
            // 从底部向上调整
            int pos = count;
            while (pos > 0 && elements[pos] < elements[(pos - 1) / 2]) {
                swap(pos, (pos - 1) / 2);
                pos = (pos - 1) / 2;
            }
            count++;
        }
    
        public void poll() {
            if (count == 0) return;
    
            //将堆底元素放入堆顶,相当于移除了堆顶元素
            elements[0] = elements[--count];
            // 从上向下进行调整
            int pos = 0;
            while (true) { 
                // 将当前节点值与左右节点的较小值进行交换
                int targetPos = pos;
                if (2 * pos + 1 < count && elements[targetPos] > elements[2 * pos + 1]) targetPos = 2 * pos + 1;
                if (2 * pos + 2 < count && elements[targetPos] > elements[2 * pos + 2]) targetPos = 2 * pos + 2;
                if (targetPos == pos) break; // 说明已经调整完了
                swap(pos, targetPos);
                pos = targetPos;
            } 
        } 
    
        public int peek() { 
            return elements[0];
        }
    
        public int size() {
            return this.count;
        }
        private void swap(int a, int b) {
            int tmp = elements[a];
            elements[a] = elements[b];
            elements[b] = tmp;
        }
    }
    

    大顶堆
    参考小顶堆实现

    class MaxHeap {
        private int capacaty;
        private int count;
        private int[] elements;
        
        public MaxHeap(int capacity) {
            this.capacaty = capacity;
            elements = new int[capacity];
        }
        
        public void insert(int num) {
            if (count >= capacaty) return;
            elements[count] = num;
            
            int pos = count;
            while (pos > 0 && elements[pos] > elements[(pos - 1) / 2]) {
                swap(pos, (pos - 1) / 2);
                pos = (pos - 1) / 2;
            }
            
            count++;
        }
        
        public Integer poll() {
            if (count <= 0) return null;
            int res = elements[0];
            
            int pos = 0;
            elements[pos] = elements[--count];
            
            while (true) {
                int targetPos = pos;
                if (2 * pos + 1 < count && elements[targetPos] < elements[2 * pos + 1]) targetPos = 2 * pos + 1;
                if (2 * pos + 2 < count && elements[targetPos] < elements[2 * pos + 2]) targetPos = 2 * pos + 2;
                if (targetPos == pos) break;
                swap(pos, targetPos);
                pos = targetPos;
            }
            
            return res;
        }
        
        private void swap(int a, int b) {
            int tmp = elements[a];
            elements[a] = elements[b];
            elements[b] = tmp;
        }
        
        public int size() {return this.count;}
        public int peek() {return elements[0];}
    }
    
    展开全文
  • C++大顶堆小顶堆

    千次阅读 2020-11-24 09:04:59
    C++大顶堆小顶堆原理大顶堆小顶堆顶堆小顶堆对比图大顶堆小顶堆的实现代码 原理   堆数据结构是一种数组对象,它可以被视为一颗完全二叉树结构(或者也有可能是满二叉树) 大顶堆   根结点(亦称为堆顶...

    原理

      堆数据结构是一种数组对象,它可以被视为一颗完全二叉树结构(或者也有可能是满二叉树)

    大顶堆

      根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大顶堆。大根堆要求根节点的关键字既大于或等于左子树的关键字值,又大于或等于右子树的关键字值。

    小顶堆

      根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者,称为小顶堆。小根堆要求根节点的关键字既小于或等于左子树的关键字值,又小于或等于右子树的关键字值。

    大顶堆和小顶堆对比图

    大顶堆和小顶堆对比图

    大顶堆和小顶堆的实现代码

    heap.h

    #pragma once
    #include<iostream>
    #include<assert.h>
    #include<vector>
    using namespace std;
    
    template<class T>
    struct Less
    {
    	bool operator()(const T& left, const T& right) const
    	{
    		return left < right;
    	}
    };
    
    template<class T>
    struct Greater
    {
    	bool operator()(const T& left, const T& right) const
    	{
    		return left > right;
    	}
    };
    
    
    template<class T, class Compare = Less<T>>
    class Heap
    {
    public:
    	Heap()//无参的构造函数(系统不会给无参构造函数),开始堆是空的不需要做什么事
    	{}
    	Heap(T* a, size_t n)
    	{
    		_a.reserve(n);//开空间
    		for (size_t i = 0; i < n; ++i)
    		{
    			_a.push_back(a[i]);
    
    		}
    		//建堆,找最后一个非叶子节点
    		for (int i = (_a.size() - 2) / 2; i >= 0; --i)//不用size_t,因为i在这可能等于0,用size_t会死循环
    		{
    			AdjustDown(i);
    		}
    	}
    	//向下调整
    	void AdjustDown(int root)
    	{
    		Compare com;
    		int parent = root;
    		size_t child = parent * 2 + 1;//默认为左孩子
    		while (child < _a.size())
    		{
    			//选出小孩子
    			//if (child+1 > _a.size() && _a[child + 1]< _a[child])
    			if (child + 1 < _a.size() && com(_a[child + 1], _a[child]))
    			{
    				++child;
    			}
    
    			//if (_a[child] < _a[parent])
    			if (com(_a[child], _a[parent]))
    			{
    				swap(_a[child], _a[parent]);//交换值
    				parent = child;
    				child = parent * 2 + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    	//向上调整
    	void AdjustUp(int child)
    	{
    		Compare com;
    		int parent = (child - 1) / 2;
    		while (parent >= 0)
    		{
    			//if (_a[child] < _a[parent])
    			if (com(_a[child], _a[parent]))
    			{
    				swap(_a[parent], _a[child]);
    				child = parent;
    				parent = (child - 1) / 2;
    			}
    			else
    			{
    				break;
    			}
    		}
    
    	}
    	//最后插入
    	void Push(const T&x)
    	{
    		_a.push_back(x);
    		AdjustUp(_a.size() - 1);
    	}
    	//删除最大数
    	void Pop()
    	{
    		assert(!_a.empty());
    		swap(_a[0], _a[_a.size() - 1]);
    		_a.pop_back();
    		AdjustDown(0);
    
    	}
    	//取顶元素
    	T& Top()
    	{
    		assert(!_a.empty());
    		return _a[0];
    	}
    	size_t Size()
    	{
    		return _a.size();
    	}
    
    	bool Empty()
    	{
    		return _a.empty();
    	}
    
    
    private:
    	vector<T> _a;
    
    };
    

    main.cpp

    #include <iostream>
    #include "heap.h"
    using namespace std;
    
    int main()
    {
    	int a[] = { 10,11,13,12,16,18,15,17,14,19 };
    	// Heap<int,Greater<int>> hp1(a,sizeof(a)/sizeof(a[0])); 最大堆
    	// Heap<int,Less<int>> hp1(a,sizeof(a)/sizeof(a[0])); 最小堆
    	Heap<int> hp1(a, sizeof(a) / sizeof(a[0])); // 缺省,最小堆
    	hp1.Push(15);
    	system("pause");
    	return 0;
    }
    

    vector和push_heap、pop_heap实现堆

    建堆

    vector<int> nums = {9, 6, 2, 4, 7, 0, 1, 8, 3, 5};
    

    如何使用nums构建最大堆

    make_heap(nums.begin(), nums.end());
    //或
    make_heap(nums.begin(), nums.end(), less<int>());
    

    如何使用nums构建最小堆

    make_heap(nums.begin(), nums.end(), greater<int>());
    

    调整堆

    当使用上述的make_heap()建完堆后,如果vector使用push_back()插入数据或pop_back()删除数据后,会破坏最大堆/最小堆的性质,所以需要调整堆,常用push_heap()和pop_heap()两个方法。
    1、push_heap()用法是,vector先push_back(),后push_heap()

    nums.push_back(10);
    push_heap(nums.begin(), nums.end(), less<int>());
    

    2、pop_heap()用法是,先pop_heap(),vector后pop_back()

    pop_heap(nums.begin(), nums.end(), less<int>());
    nums.pop_back();
    

    为什么pop_heap()的用法要反过来呢?
    要从我们的目的来考虑,使用pop_heap()的绝大部分目的是要把堆顶元素pop出堆中,因为它最大或最小。如果先用vector的pop_back(),它删除的不是堆顶元素(nums[0]),而是vector的最后一个元素。可见这不是我们想要的结果:对于最大堆,最后一个元素既不是最大,也不一定是最小;对于最小堆,最后一个元素既不是最小,也不一定是最大。pop出来没有意义。
    观察pop_heap()对堆做了什么?
    pop_heap()把堆顶元素放到了最后一位,然后对它前面的数字重建了堆。这样一来只要再使用pop_back()把最后一位元素删除,就得到了新的堆。

    priority_queue实现堆

    priority_queue
    对于这个模板类priority_queue,它是STL所提供的一个非常有效的容器。
    作为队列的一个延伸,优先队列包含在头文件 中。

    简述

    优先队列时一种比较重要的数据结构,它是有二项队列编写而成的,可以以O(log n) 的效率查找一个队列中的最大值或者最小值,其中是最大值还是最小值是根据创建的优先队列的性质来决定的。

    模板参数

    优先队列有三个参数,其声明形式为:

    priority_queue< type, container, function >
    

    这三个参数,后面两个可以省略,第一个不可以。其中:
    **type:**数据类型;
    **container:**实现优先队列的底层容器;
    **function:**元素之间的比较方式;
    对于container,要求必须是数组形式实现的容器,例如vector、deque,而不能使list。
    在STL中,默认情况下(不加后面两个参数)是以vector为容器,以 operator< 为比较方式,所以在只使用第一个参数时,优先队列默认是一个最大堆,每次输出的堆顶元素是此时堆中的最大元素。

    成员函数

    假设type类型为int,则:

    1. bool empty() const 返回值为true,说明队列为空;
    2. int size() const 返回优先队列中元素的数量;
    3. void pop() 删除队列顶部的元素,也即根节点;
    4. int top() 返回队列中的顶部元素,但不删除该元素;
    5. void push(int arg) 将元素arg插入到队列之中。

    大顶堆和小顶堆

    #include <functional>
    
    //构造一个空的优先队列(此优先队列默认为大顶堆)
    priority_queue<int> big_heap;   
    //另一种构建大顶堆的方法
    priority_queue<int,vector<int>,less<int> > big_heap2; 
    
    //构造一个空的优先队列,此优先队列是一个小顶堆
    priority_queue<int,vector<int>,greater<int> > small_heap;  
    
    展开全文
  • 小顶堆排序

    2020-07-22 21:03:19
    小顶堆排序 public class 小顶堆输出 { /* 小顶堆分两大步:1堆化2排序 *堆化: 最重要的分为三段 * 1。考虑边界问题; * 2、比较左右孩子更的; * 3、找到了换还是不换的问题。 */ public static void...

    小顶堆排序

    public class 小顶堆输出 {
    	/* 小顶堆分两大步:1堆化2排序
    	 *堆化: 最重要的分为三段
    	 * 1。考虑边界问题;
    	 * 2、比较左右孩子更小的;
    	 * 3、找到了换还是不换的问题。
    	 */
    public static void main(String[] args) {
    	int arr[]={78,56,34,43,4,1,15,2,23};
    	sort(arr);
    	for(int i=0;i<arr.length;i++) {
    		System.out.print(arr[i]+" ");
    	}
    }
    private static void MinHeap(int[] arr) {
    	// TODO Auto-generated method stub
    	int n=arr.length;
    	for(int i=n/2-1;i>=0;i--) {//保证每个节点作为根节点的时候,都是小顶堆
    		FixDown(arr,i,n); //把i做为根节点
    	}
    }
    private static void FixDown(int[] arr, int i, int n) {
    	// TODO Auto-generated method stub
    	//找到左右孩子                                      1.设边界
    	int left=2*i+1;
    	int right=2*i+2;
    	//如果左孩子越界,I就是叶子节点
    	if(left>=n) {
    		return;
    	}
    	int min=left;
    	//如果右孩子越界,I就是叶子节点
    	if(right>=n) {
    		min=left;
    	}else {      //走到这,左右孩子都没有越界。                 
    		if(arr[right]<arr[left]) {//2.比较左右孩子
    			min=right;
    		}
    	}
    	//如果A[i]比两个孩子都要小,不用调整         3.考虑要不要换
    	if(arr[i]<=arr[min]) {
    		return;
    	}
    	//否则,找到两个孩子中较小的,和i交换        4.换
    	int temp=arr[i];//拷贝最小的值
    	arr[i]=arr[min];
    	arr[min]=temp;
    	//小孩子的那个位置的值发生了变化,I变得更为小那个位置
    	FixDown(arr,min,n); 
    }
    private static void sort(int arr[]) {
    	//先堆化
    	MinHeap(arr);
    	//把堆顶,0号元素和最后一个元素交换
    	for(int x=arr.length-1;x>=0;x--) {
            swap(arr, 0, x);
    		FixDown(arr,0,x);
    	}
    	//缩小堆的范围,对堆顶元素进行向下调整	
    }
    public static int[]  swap(int arr[],int sp,int bigger) {
    	/*数组两个元素位置互换*/
           int temp=arr[sp];
           arr[sp]=arr[bigger];
           arr[bigger]=temp;
    	return arr;	   //将数组返回—    
    }
    }
    
    
    展开全文
  • PriorityQueue小顶堆

    千次阅读 2018-05-04 09:00:54
    Java中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。PriorityQueue位于Java util包中,观其名字前半部分的单词Priority是优先的意思,实际上这个队列就是具有“优先级”。既然具有优先级的特性,...

    Java中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示PriorityQueue位于Java util包中,观其名字前半部分的单词Priority是优先的意思,实际上这个队列就是具有“优先级”。既然具有优先级的特性,那么就得有个前后排序的“规则”。所以其接受的类需要实现Comparable 接口。该队列线程安全,不允许null值,入队和出队的时间复杂度是O(log(n))。

    对于大根堆,就要借助于comparator比较器,来实现大根堆。(使用默认的初始容量:11)

    [java]  view plain  copy
    1. PriorityQueue <Integer> maxHeap = new PriorityQueue<Integer>(11new Comparator<Integer>() {  
    2.   
    3.     @Override  
    4.     public int compare(Integer o1, Integer o2) {  
    5.         // TODO Auto-generated method stub  
    6.         return o2.compareTo(o1);  
    7.     }  
    8.       
    9. });  

    API

    1.构造函数

    PriorityQueue()
    PriorityQueue(Collection<? extends E> c)
    PriorityQueue(int initialCapacity)
    PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
    PriorityQueue(PriorityQueue<? extends E> c)
    PriorityQueue(SortedSet<? extends E> c)

    2.常用功能函数

    方法名功能描述
    add(E e)添加元素
    clear()清空
    contains(Object o)检查是否包含当前参数元素
    offer(E e)添加元素
    peek()读取元素,(不删除)
    poll()取出元素,(删除)
    remove(Object o)删除指定元素
    size()返回长度

    方法剖析

    add()和offer()

    add(E e)offer(E e)的语义相同,都是向优先队列中插入元素,只是Queue接口规定二者对插入失败时的处理不同,前者在插入失败时抛出异常,后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。

    PriorityQueue_offer.png

    新加入的元素可能会破坏小顶堆的性质,因此需要进行必要的调整。

    //offer(E e)
    public boolean offer(E e) {
        if (e == null)//不允许放入null元素
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);//自动扩容
        size = i + 1;
        if (i == 0)//队列原来为空,这是插入的第一个元素
            queue[0] = e;
        else
            siftUp(i, e);//调整
        return true;
    }

    上述代码中,扩容函数grow()类似于ArrayList里的grow()函数,就是再申请一个更大的数组,并将原数组的元素复制过去,这里不再赘述。需要注意的是siftUp(int k, E x)方法,该方法用于插入元素x并维持堆的特性。

    //siftUp()
    private void siftUp(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

    新加入的元素x可能会破坏小顶堆的性质,因此需要进行调整。调整的过程为:k指定的位置开始,将x逐层与当前点的parent进行比较并交换,直到满足x >= queue[parent]为止。注意这里的比较可以是元素的自然顺序,也可以是依靠比较器的顺序。

    element()和peek()

    element()peek()的语义完全相同,都是获取但不删除队首元素,也就是队列中权值最小的那个元素,二者唯一的区别是当方法失败时前者抛出异常,后者返回null。根据小顶堆的性质,堆顶那个元素就是全局最小的那个;由于堆用数组表示,根据下标关系,0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可

    PriorityQueue_peek.png

    代码也就非常简洁:

    //peek()
    public E peek() {
        if (size == 0)
            return null;
        return (E) queue[0];//0下标处的那个元素就是最小的那个
    }

    remove()和poll()

    remove()poll()方法的语义也完全相同,都是获取并删除队首元素,区别是当方法失败时前者抛出异常,后者返回null。由于删除操作会改变队列的结构,为维护小顶堆的性质,需要进行必要的调整。

    PriorityQueue_poll.png
    代码如下:

    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];//0下标处的那个元素就是最小的那个
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);//调整
        return result;
    }

    上述代码首先记录0下标处的元素,并用最后一个元素替换0下标位置的元素,之后调用siftDown()方法对堆进行调整,最后返回原来0下标处的那个元素(也就是最小的那个元素)。重点是siftDown(int k, E x)方法,该方法的作用是k指定的位置开始,将x逐层向下与当前点的左右孩子中较小的那个交换,直到x小于或等于左右孩子中的任何一个为止

    //siftDown()
    private void siftDown(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            //首先找到左右孩子中较小的那个,记录到c里,并用child记录其下标
            int child = (k << 1) + 1;//leftNo = parentNo*2+1
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;//然后用c取代原来的值
            k = child;
        }
        queue[k] = x;
    }

    remove(Object o)

    remove(Object o)方法用于删除队列中跟o相等的某一个元素(如果有多个相等,只删除一个),该方法不是Queue接口内的方法,而是Collection接口的方法。由于删除操作会改变队列结构,所以要进行调整;又由于删除元素的位置可能是任意的,所以调整过程比其它函数稍加繁琐。具体来说,remove(Object o)可以分为2种情况:1. 删除的是最后一个元素。直接删除即可,不需要调整。2. 删除的不是最后一个元素,从删除点开始以最后一个元素为参照调用一次siftDown()即可。此处不再赘述。

    PriorityQueue_remove2.png

    具体代码如下:

    //remove(Object o)
    public boolean remove(Object o) {
        //通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
        int i = indexOf(o);
        if (i == -1)
            return false;
        int s = --size;
        if (s == i) //情况1
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);//情况2
            ......
        }
        return true;
    }

    用法示例

    上面提到具有优先级,那么这里举个例子。我在上高中的时候,每月分一次班级,老师会按照本月月考的成绩来让每位同学优先选择自己心仪的座位。这里所有的同学便是一个队列;每次喊一个人进来挑选座位,这便是出对的操作;成绩由前至后,这边是优先的策略。

    • 代码示例如下:
    public class PriorityQueueTest {
        public static void main(String[] args) {
                    
            final PriorityQueue<Student> queue=new PriorityQueue<>();
    
            Student p1=new Student(95,"张三");
            Student p2=new Student(89,"李四");
            Student p3=new Student(89,"李四");
            Student p4=new Student(67,"王五");
            Student p5=new Student(92,"赵六");
            queue.add(p1);
            queue.add(p2);
            queue.add(p3);//add 和offer效果一样。
            queue.offer(p4);//add 方法实现,其实就是调用了offer
            queue.offer(p5)
    
            for (Student Student : queue) {
                System.out.println(Student.toString());
            }
            
            System.out.println("---------------------");
            while(!queue.isEmpty()){
                System.out.println(queue.poll());
            }       
        }
    
    }
    class Student implements Comparable{
        private int score;
        private String name;
        
        public Student(int age,String name){
            this.score=age;
            this.name=name;
        }
        public int getScore() {
            return score;
        }
        public void setScore(int score) {
            this.score = score;
        }
        public String getName() {
            return name;
        }
        public void setName(String name) {
            this.name = name;
        }
        public String toString(){
            return "姓名:"+name+"-"+score+"分";
        }
    
        @Override
        public int compareTo(Object o) {
            Student current=(Student)o;
            if(current.getScore()>this.score){
                return 1;
            }else if(current.getScore()==this.score){
                return 0;
            }
            return -1;
        }
    }
    • 运行结果:
      姓名:张三-95分
      姓名:赵六-92分
      姓名:王五-67分
      姓名:李四-89分
      ---------按顺序出队选座位------------
      姓名:张三-95分
      姓名:赵六-92分
      姓名:李四-89分
      姓名:李四-89分
      姓名:王五-67分

    从第一部分输出可以看出,学生入队并不是 按顺序的,而在poll出来的时候是按顺序出队的,这里确实实现了分数高这优先选座位的效果,poll方法返回的总是队列剩余学生中分数最高的。

    安全性

    查看PriorityQueue类的源码,会发现增加操作,并不是原子操作。没有使用任何锁。那么,如果是在多线程环境,肯定是不安全的。下面给出例子,开启多个线程,调用同一个方法对Queue进行添加元素。然后输出结果。

    public class PriorityQueueTest {
    
        static final PriorityQueue<Integer> queue=new PriorityQueue<>();
        /**
         * 向队列中插入元素
         * @param number
         */
        public  void add(int number){
            if(!queue.contains(number)){
                System.out.println(Thread.currentThread()+":"+number);
                queue.add(number);
            }
        }   
    
    public static void main(String[] args) throws InterruptedException {
        final PriorityQueueTest qt=new PriorityQueueTest();
            final Random r=new Random();
            Thread t1=new Thread(){
                public void run(){
                    System.out.println("t1开始运行...");
                    for(int i=0;i<10;i++){
                        qt.add(r.nextInt(10));
                    }
                }
            };
            Thread t2=new Thread(){
                public void run(){
                    System.out.println("t2开始运行...");
                    for(int i=0;i<10;i++){
                        qt.add(r.nextInt(10));
                    }
                }
            };
            Thread t3=new Thread(){
                public void run(){
                    System.out.println("t3开始运行...");
                    for(int i=0;i<10;i++){
                        qt.add(r.nextInt(10));
                    }
                }
            };
            t1.start();
            t2.start();
            t3.start();
            t1.join();
            t2.join();
            t3.join();
            System.out.println("------ 运行结果 ---------");
            while(!queue.isEmpty()){
                System.out.println(queue.poll());
            }
        }
    }
    • 运行结果
      t2开始运行...
      t3开始运行...
      t1开始运行...
      ------ 运行结果 ---------
      0
      1
      1
      2
      3
      4
      5
      6
      7
      8
      9
      9

    结果中我们可以看到,具有两个1,两个9.这是不符合我们预期的,我们预期的是not contains 才插入,现在的出现的了重复的。上面的例子只需要在add方法上加锁,才可以达到我们预期的效果。所以说,PriorityQueue非线程安全的。

    展开全文
  • 顶堆代码、小顶堆代码 实际应用及实例代码 小顶堆删除图解代码、插入代码 小顶堆插入图解 时间复杂度分析 1、百度-》概念:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种...
  • 通俗解释大顶堆小顶堆

    千次阅读 2020-12-17 21:28:35
    基础数据结构 ...大顶堆小顶堆 我们知道大顶推满足的条件是每一个父节点都比子节点大。 那么我们应该如何通过调换节点的位置来构建这样的数据结构呢? 我们取这个树的一个片段,假设数据为2,1,3。那.
  • 熟悉数据结构的同学都知道,堆排序是一种利用堆数据结构而设计的算法,它的最好最差...这里我们用TS自带的数组来存储数据,在每次插入新数据时进行向下调整操作。而在弹出数据时,对顶部的数据进行下移操作,代码具...
  • C++小顶堆求Topk

    千次阅读 2017-10-15 20:17:37
    C++小顶堆求Topk求数组中的Topk数字,比如【1、4、6、7、2、9、8、3、5、0】...然后逐个将剩余数字与堆顶比较,如果大于堆顶,则与堆顶交换,并向下调整堆。 最后堆中保存的就是最大的4个数字。 代码如下,MinHeap.cpp
  • 非优先队列的小顶堆

    2020-05-15 10:59:37
    对应两种操作,尾部插入元素和删除顶堆元素,当删除了顶堆元素时,把尾部元素赋值给顶部位置,然后删除尾部元素,然后再向下调整堆; 对应代码 #include<iostream> using namespace std; const int MAXN=1e6+5...
  • 首先了解 PriorityQueue(优先队列) 是一个基于优先级堆的无界优先级队列,...随着不断优先级队列添加元素,其容量会自动增加 PriorityQueue 线程不安全,想线程安全用 PriorityBlockingQueue 类 PriorityQueue
  • Java实现 大顶堆小顶堆

    千次阅读 2017-06-06 22:53:28
    1、大顶堆 package jianzhiOffer; import java.util.ArrayList; import java.util.List; /** * 大顶堆 * * @author tao * */ public class MaxHeap> { private List mHeap; // 存放元素的动态数组 public...
  • 数组实现小顶堆

    2020-04-09 20:42:24
    然后不断向下交换直到没有大小颠倒位置。 * @return */ public static int pop() { // 最小值 int ret = heap[0]; // 要提到根的值 int x = heap[--size]; // 从根开始向下交换 int i = 0; while (i*2+1 ) { // 比较...
  • 这棵树有一个很显著的特点,那就是所有父结点都要比子结点要。符合这样要求的完全二叉树我们成为“最小堆”。反之,如果所有父结点都要比子结点大,这样的完全二叉树被称为”最大堆“。 2.下移ShiftDown 如果...
  • 堆排序的思想这里就先不讲了,以后有时间再补上,下面是分别采用大顶堆小顶堆实现的堆排序。 注意:下面例子中排序的数字是{1,2,5,3,6,4,9,7,8}。 大顶堆方式 #include &lt;iostream&gt; #include &...
  • 这里写目录标题一、堆排序小顶堆举个栗子大顶堆二、前K个高频元素思路分析三、大顶堆小顶堆代码解析 一、堆排序 要了解大顶堆小顶堆,我们先简单了解一下堆排序。 堆排序(Heapsort)是指利用堆这种数据结构设计的...
  • 数据结构 小顶堆建堆过程 构建过程

    千次阅读 2021-02-26 18:35:22
    【一】简介 最小堆是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子的值。本文以图解的方式,说明最小堆的构建、插入、删除的过程...根据性质,的数字往上移动;至此,第1次调整完成。 注意,被调整的节点...
  • 顶堆 :  逻辑结构:  1颗完全二叉树,结点的值大于其左右两个字节点的值。 存储结构:  单一结点值的可以使用数组存储。例如数组int[] a从 下标1开始存储结点值。则 大顶堆满足 a[i] >= a[2 * i],a[i] >= a[2...
  • 链接:POJ1456 思路:贪心策略+小顶堆数据结构 思路来源于算法进阶指南,我们的目的是在t的...2 : 如果当前商品的过期时间等于堆内商品总数,就将该商品与顶堆堆顶的节点利润进行比较,如果大于堆顶利润则替换,并
  • topk--堆排序--小顶堆

    千次阅读 2016-07-14 07:58:54
    ②如果此数>堆顶的数,则将此数和堆顶的数交换,然后从堆顶向下调整堆,使其重新满足小顶堆。 【说明】堆的存储 一般用数组来表示堆,第i个节点的父节点下标为i/2-1;它的左右节点下标分别为:2*i+1和2*1+2 ...
  • Java 堆排序(大顶堆小顶堆)

    万次阅读 2018-07-10 21:51:17
    //调整小顶堆 /*调整自顶向下 * 只要孩子节点比父节点的值大,就进行值交换, */ int left=index* 2 ; int right=index* 2 + 1 ; int max= 0 ; if (left< 10 &&arr[left][index]){ max=...
  • 顶堆升序、小顶堆降序的堆排序(以Java描述为例版本) 一、定义 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,...
  • 堆排序(小顶堆

    2019-03-05 10:09:00
    本题旨在测试各种不同的排序算法在各种数据情况的表现。各组测试数据特点如下: 数据1:只有1个元素; 数据2:11个不相同的整数,测试基本正确性; 数据3:103个随机整数; 数据4:104...
  • 小顶堆排序的实现

    千次阅读 2014-05-07 15:04:16
    /* 向下调整主要用于排序*/ void heap_shift_down(int *ptr,int pos, int len) { int min; //设置最小元素下标 int index = pos; while (index*2+1 ) { min = index * 2+1; if (index*2+2 )// 存在右节点 { ...
  • 文章目录1.堆的定义2.堆排序3.在堆排序中:如何初始化一个序列来建堆 ...eg:(1){12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 是小顶堆,why? 首先按照将这些数列,按照层次遍历的顺序,构造成完全二叉树; ...
  • 什么是大/小顶堆? 大/根堆的实现可以看似为一颗完全二叉树,但和完全二叉树还是有区别的(具体的完全二叉树在之后会讲。 堆顶元素为整个堆的最大/元素。 使用情景? 局部元素排序、实现优先队列、SPFA优化 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,679
精华内容 3,071
关键字:

小顶堆向下调整