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

    2016-09-08 01:33:24
    // MinStack - 小顶堆 - 开始 template<typename T> class MinHeap { int maxHeapSize; T * heap; int currentSize; void shiftDown(int start, int end) { ...
        
    // MinStack - 小顶堆 - 开始
    template<typename T>
    class MinHeap {
        int maxHeapSize;
        T * heap;
        int currentSize;
        void shiftDown(int start, int end) {
            T temp = heap[start];
            while(true) {
                int j = 2*start+1;
                if(j > end) break;
                if(j < end && heap[j] > heap[j+1]) j++;
                if(temp <= heap[j]) break;
                heap[start] = heap[j];
                start = j;
            }
            heap[start] = temp;
        }
        void shiftUp(int start) {
            T temp = heap[start];
            while(start > 0) {
                int i = (start-1)/2;
                if(heap[i] <= temp) break;
                heap[start] = heap[i];
                start = i;
            }
            heap[start] = temp;
        }
    public:
        MinHeap(int size = 10000) {
            heap = new T[maxHeapSize = size];
            currentSize = 0;
        }
        ~MinHeap() {
            delete[] heap;
        }
        bool isEmpty() {
            return currentSize == 0;
        }
        bool isFull() {
            return currentSize == maxHeapSize;
        }
        void clear() {
            currentSize = 0;
        }
        void insert(T x) {
            heap[currentSize] = x;
            shiftUp(currentSize++);
        }
        T remove() {
            T x = heap[0];
            heap[0] = heap[--currentSize];
            shiftDown(0, currentSize-1);
            return x;
        }
    };
    // MinStack - 小顶堆 - 结束
    template<typename T>
    class priority_queue {
        std::vector<T> data;
        bool (*_comp)(T, T);
    public:
        priority_queue(bool (*comp)(T, T) = NULL) {
            _comp = comp;
        }
        priority_queue(T *from, T *to, bool (*comp)(T, T) = NULL) {
            _comp = comp;
            data.assign(from, to);
            _comp ? std::make_heap(data.begin(), data.end(), *this)
                  : std::make_heap(data.begin(), data.end());
        }
        bool operator() (T a, T b) {
            return _comp && _comp(a, b);
        }
        void push(T t) {
            data.push_back(t);
            _comp ? std::push_heap(data.begin(), data.end(), *this)
                  : std::push_heap(data.begin(), data.end());
        }
        void pop() {
            _comp ? std::pop_heap(data.begin(), data.end(), *this)
                  : std::pop_heap(data.begin(), data.end());
            data.pop_back();
        }
        void sort() {
            _comp ? std::sort_heap(data.begin(), data.end(), *this)
                  : std::sort_heap(data.begin(), data.end());
        }
        T top() {
            return data.front();
        }
        int size() {
            return data.size();
        }
    };
    展开全文
  • 学生,代码资源,希望大家能有用。
  • 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-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];}
    }
    
    展开全文
  • 大顶堆和小顶堆

    2020-02-26 17:41:04
    其实大顶堆就是arr[n]>=arr[2n+1] && arr[n]>=arr[2n+2] 这个就是利用数组存储树的条件。 小顶堆是把 > 换车<即可。

    堆排序还是选择排序
    其实大顶堆就是arr[n]>=arr[2n+1] && arr[n]>=arr[2n+2] 这个就是利用数组存储树的条件。
    小顶堆是把 > 换车<即可。

    堆是具有以下特点的完全二叉树
    不是满足上边的第一个条件,就是满足第二个条件。

    package a;
    
    public class HeapSortDemo {
        public static void main(String[] args) {
            int[] arr = {4, 6, 5, 8, 9};
            heapSort(arr);
        }
    
        private static void heapSort(int[] arr) {
    
        }
    
        private static void swap(int[] arr, int index,int len) {
            int temp = arr[index];
            for(int k = index*2+1;k<len;k = k*2+1) {//已经是移动后的子节点了
                if ((k+1)<len&&arr[k] < arr[k + 1]) {
                    k++;//也就是找到那个最大值。
                }
    
                if (arr[k] > temp) {//总是跟最初的那个值比较。也就是子节点的值
                    arr[index]=arr[k];//将大的值移动到父节点
                    index=k;//占领移动后的位置。
                }else {
                    break;
                }
            }
            arr[index] = temp;
    
    
    
        }
    }
    
    

    这个代码用于生成大顶堆。

    展开全文
  • 下面小编就为大家分享一篇Java 堆排序实例(大顶堆、小顶堆),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 小顶堆大顶堆

    2017-03-21 11:33:02
    L2-012. 关于堆的判断 时间限制 400 ms 内存限制 65536 kB ...将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种: “x is
  • 小顶堆排序

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

    2020-03-20 11:02:50
    一、大顶堆和小顶堆的原理 1、大顶堆 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大顶堆。大根堆要求根节点的关键字既大于或等于左子树的关键字值,又大于或等于右子树的关键字值。 2、...
  • 小顶堆和大顶堆

    千次阅读 2017-11-05 19:26:26
     小顶堆-木柴切割 这是一道小顶堆的模板题,和合并果子一模一样差不多。  题目描述  FarmerJohn想修理牧场栅栏的某些小段。为此,他需要N(1  FJ郁闷地发现,他并没有锯子来把这块长木板锯开。于是他把这块长...
  • 大顶堆及堆顶元素为整个堆中的最大值,小顶堆同理,它可以在O(1)时间内获取最大值。下面以大顶堆讲解一些堆的相关知识,并给出大、小顶堆的代码。 首先,既然是顺序存储,且又是完全二叉树的结构,其节点如何存储呢...
  • 堆-大顶堆小顶堆

    2020-05-02 08:32:41
    目录堆的定义堆的相关操作插入元素删除顶点元素 堆的定义 是一个完全二叉数 堆中的每个节点都必须大于或小于其子树所以节点的值。...每个节点小于其子树节点的堆叫做小顶堆 堆的相关操作 插入元素 删除顶点元素 ...
  • 首先明确堆是一个完全二叉树,小顶堆指根结点的值小于或等于左右子节点的值,大顶堆指根结点的值都大于或等于左右子节点的值 关于大小顶堆的建立更详细的介绍 #include<iostream> #include<cstdio> #...
  • 按照堆的特点可以把堆分为大顶堆和小顶堆 大顶堆:每个结点的值都大于或等于其左右孩子结点的值 小顶堆:每个结点的值都小于或等于其左右孩子结点的值 使用堆的原因? 如果仅仅是需要得到一个有序的序列,使用排序就...
  • 大顶堆和小顶堆--Java版

    千次阅读 2017-08-11 16:01:04
    目录:1、前期参考2、大顶堆原理3、小顶堆原理4、大顶堆和小顶堆对比图5、大顶堆代码6、执行结果————————————————————————————-1、前期参考使用一维数组存储二叉树 ...
  • 谈谈堆排序,大顶堆,小顶堆
  • C++小顶堆的实现,其中用到了类模板的知识,代码附有详细注释,主函数中附上了测试代码。欢迎私信讨论!
  • 基础数据结构 ...大顶堆和小顶堆 我们知道大顶推满足的条件是每一个父节点都比子节点大。 那么我们应该如何通过调换节点的位置来构建这样的数据结构呢? 我们取这个树的一个片段,假设数据为2,1,3。那.
  • 排序算法——小顶堆

    千次阅读 2018-10-16 17:30:09
    一、小顶堆原理 小顶堆实际上是一个二叉树,满足:Key[i]&amp;lt;=key[2i+1]&amp;amp;&amp;amp;Key[i]&amp;lt;=key[2i+2]规则,即根节点既小于或等于左子树的关键字值,又小于或等于右子树的关键字...
  • 在含有 n 个元素的小顶堆中增加一个元素且调整为新的小顶堆。 算法:由于原来 n 个元素已经是堆,所以调整时仅需从 A[n+1]出发,走一条从叶子结点 A[n+1] 到根结点 A[1]的路径,将该结点与其父亲结点比较,若比父亲...
  • 大顶堆代码、小顶堆代码 实际应用及实例代码 小顶堆删除图解代码、插入代码 小顶堆插入图解 时间复杂度分析 1、百度-》概念:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种...
  • 小顶堆 任何一非叶节点的关键字不小于其左右孩子节点的关键字,最顶端节点一定是序列中最小元素 堆排序算法 流程: 1)构造一个完全二叉树 2)将该树构建为大顶堆 3)将根节点与最后一个元素交换位置 4)将剩下的...
  • 按照堆的特点可以把堆分为大顶堆和小顶堆 大顶堆:每个结点的值都大于或等于其左右孩子结点的值 小顶堆:每个结点的值都小于或等于其左右孩子结点的值 (堆的这种特性非常的有用,堆常常被当做优先队列使用,因为...
  • PriorityQueue小顶堆

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

    千次阅读 2019-09-14 15:20:11
    堆是一种非线性结构,(本篇随笔主要分析堆的数组实现)可以把堆看作一个数组,也可以被看作一个完全二叉树,通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组,按照堆的特点可以把堆分为大顶堆和小顶堆。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,862
精华内容 1,944
关键字:

小顶堆