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

    千次阅读 2015-04-23 13:57:46
    该数据结构满足首为中的最小元素,二叉树中的所有父节点都比子节点的要小。 首先要讨论的问题是构建 1从0开始构建,直接一项一项的添加进 这是一个动态添加的过程,每次添加都假设现在的满足最大的...

    一种常见的数据结构,内部用二叉树的结构存储着数据,由于该二叉树满足完全二叉树的定义,所以我们可以通过数组来实现二叉树的存储。该数据结构满足堆首为堆中的最小元素,二叉树中的所有父节点都比子节点的要小。

    首先要讨论的问题是构建堆

    1从0开始构建,直接一项一项的添加进堆

    这是一个动态添加的过程,每次添加都假设现在的堆满足最大堆的定义,每次添加一项我们就需要把它放到合适的位置。一个很初始的想法就是把节点放在完全二叉树的下一个节点上,如果不满足最小堆的定义再调整,此时我们发现冲突点转移到了高度为1层的节点上,那么我们把新添加的节点与父节点比较,如果存在冲突,我们就交换两者位置,此时高度为0与1层的节点之间的关系满足了最小堆定义,此时矛盾转义到了高度为2层的节点上,重复之前的操作,此时我们会发现高度为0,1,2的层满足最小堆的定义,依次我们可以推到树的根节点。  


    2从一个已有数组开始构建

    这里也可以通过动态构建,假设目前数组可以构成一个高度为h的二叉树,我们可以通过从高度为1的最小堆开始构建,然后利用高度为1的最小堆构建高度为2的最小堆,一直到高度为h的最小堆,这个过程中每个分析单元 我们只需要考虑将堆的根节点放到合适的位置,这样新构造的堆肯定能满足最小堆的要求。


    其次要考虑的问题是取元素的过程

    我们需要拿出去的元素肯定是堆首,但是当我们拿出堆首之后,这个堆就存在着一个空槽,我们的问题是怎么填补这个空槽,我一个直接的想法是取子节点中最小的元素来填补空槽,那么空槽就会被推到下一层,但是存在着一个问题,当我们把空槽推到最底层的时候我们要选择哪个元素去填补这个空槽,由于需要满足完全二叉树,那么我们很自然的想到拿出最后一个元素填充这个空槽,但是注意这样填补了可能导致整个堆不满足最小堆的定于,我们需要处理这个元素比父元素大的情况,使他一路上浮到该有的位置,

    这个过程其实是和直接拿最后的元素填充到堆首并且将该元素推到该有的位置是等价的。


    另外需要考虑的就是关于最小堆的一些有意义的操作了,其中一个就是实现优先队列,普通的进队出队操作和最小堆的进堆出堆操作是一致的,剩下需要考虑的就是提高和降低优先级的操作,这个在最小堆中实现也很简单,只是降低或增加排序键值的值,我们可以通过一次线性搜索找到需要操作的对象,然后通过一次堆排序来实现


    对于最小堆来说  进堆操作和出堆操作的时间复杂度都是O(log(n)),也就是元素需要上浮或者下潜log(n)层,但是构建一个最小堆的过程时间复杂度为O(n)  总的来说效率还是很高的


    package 最小堆;
    
    public class MinHeap {
    
    	public static void main(String[] args) {
    		MinHeap minHeap = new MinHeap(7);
    		int[] array = { 4, 3, 2, 1, 5, 7 };
    		int k = 6;
    		minHeap.buildup(array, k);
    		minHeap.addElement(6);
    		minHeap.increasePriority(6, 10);
    		minHeap.decreasePriority(2, 8);
    		minHeap.deleteInnode(3);
    		while(minHeap.hasMore()){
    			System.out.println(minHeap.pushoutHeapHead());
    		}
    	}
    
    	int[] heap; // 0号位弃用 来实现二叉树到数组的映射
    	int heapSize; // 记录堆的大小
    	private int MaxSize; // 记录堆的最大大小
    
    	public MinHeap(int defaultSize) {
    		heap = new int[defaultSize + 1];
    		heapSize = 0;
    		MaxSize = defaultSize;
    	}
    
    	// 把元素向上推到合适位置
    	private void pushUp(int index) {
    		while (index > 1) {
    			if (heap[index] < heap[index >> 1]) {
    				int temp = heap[index];
    				heap[index] = heap[index >> 1];
    				heap[index >> 1] = temp;
    				index = index >> 1;
    			} else {
    				return;
    			}
    		}
    	}
    
    	// 把元素向下推到合适的位置
    	private void pollDown(int index) {
    		int OrNum = -1;
    		if ((index << 1) <= heapSize && heap[index] > heap[index << 1]) {
    			OrNum = 0;
    		}
    
    		if ((index << 1 | 1) <= heapSize && heap[index] > heap[index << 1 | 1]) {
    			if (OrNum > -1 && heap[index << 1] < heap[index << 1 | 1]) {
    
    			} else {
    				OrNum = 1;
    			}
    		}
    		if (OrNum >= 0) {
    			int temp = heap[index];
    			heap[index] = heap[index << 1 | OrNum];
    			heap[index << 1 | OrNum] = temp;
    			pollDown(index << 1 | OrNum);
    		} else {
    			return;
    		}
    	}
    
    	// 传入参数K表示 数组的前k个初始化成堆,另外要求k要小于堆的最大大小
    	// 结果为 最后类中存在着一个大小为K的堆
    	public void buildup(int[] inputArray, int k) {
    		for (int i = 0; i < k; i++) {
    			heap[i + 1] = inputArray[i];
    		}
    		heapSize = k;
    		int index = Integer.highestOneBit(k) - 1;
    		while (index > 0) {
    			pollDown(index);
    			index--;
    		}
    	}
    
    	// 向堆中添加元素
    	public void addElement(int inNum) {
    		heapSize++;
    		heap[heapSize] = inNum;
    		pushUp(heapSize);
    	}
    
    	// 将堆首推出堆
    	public int pushoutHeapHead() {
    		int reVal = heap[1];
    		heap[1] = heap[heapSize];
    		heapSize--;
    		pollDown(1);
    		return reVal;
    	}
    
    	// 辅助取出堆首
    	public boolean hasMore() {
    		return heapSize > 0;
    	}
    
    	// 这个方法是通过key 找到节点,将该节点的优先级降低
    	// 由于目前实现中的key和优先级一致可能不明显,但是可以用这样的结构实现任务调度
    	public void decreasePriority(int key, int value) {
    		for (int i = 1; i <= heapSize; i++) {
    			if (heap[i] == key) {
    				heap[i] += value;
    				pollDown(i);
    				return;
    			}
    		}
    	}
    
    	public void increasePriority(int key, int value) {
    		for (int i = 1; i <= heapSize; i++) {
    			if (heap[i] == key) {
    				heap[i] -= value;
    				pushUp(i);
    				return;
    			}
    		}
    	}
    
    	public void deleteInnode(int key) {
    		for (int i = 1; i <= heapSize; i++) {
    			if (heap[i] == key) {
    				heap[i] = heap[heapSize];
    				heapSize--;
    				pollDown(i);
    				return;
    			}
    		}
    	}
    }
    


    展开全文
  • 最小堆最小堆排序

    千次阅读 2016-04-13 14:28:10
    2、最小堆的构造和添加#include #define N 9 // 最小堆得元素个数int minHeap[N]; // 存放最小堆的数组 int index1 = 0; // 最小堆数组索引void add(int d) // 向最小堆内添加数据 { if(index1 >= N) { printf(...

    1、原理介绍:百度百科
    2、最小堆的构造和添加

    #include <stdio.h>
    #define N 9 // 最小堆得元素个数
    
    int minHeap[N]; // 存放最小堆的数组
    int index1 = 0; // 最小堆数组索引
    
    void add(int d) // 向最小堆内添加数据
    {
        if(index1 >= N)
        {
            printf("Out of range!\n");
            return;
        }
        int t = index1; // t指向存放位置
        int pt = (t - 1) / 2; // 父节点
        while(t > 0) // t指向0位置时结束循环
        {
            if(minHeap[pt] > d) // 当父节点数据比插入数据大时,将父节点数据下移
            {
                minHeap[t] = minHeap[pt];
                t = pt;
                pt = (t - 1) / 2;
            }
            else // 找到合适位置
                break;
        }
        minHeap[t] = d; // 最后存放数据位置
        index1++;
    }
    int main()
    {
        int t[9] = {2, 1, 7, 3, 17, 19, 36, 25, 100};
        int i;
        for(i=0; i<9; i++)
        {
            add(t[i]);
        }
    
        for(i=0; i<9; i++) // 输出测试
        {
            printf("%d ", minHeap[i]);
        }
        printf("\n");
        return 0;
    }

    3、最小堆排序算法
    在构造最小堆时,没有必要一个节点一个节点的添加,可以将原来的数组看成一颗完全二叉树。并且知道数组元素个数。那么从最后一个非叶子节点的节点开始逐步向前,直到第一个节点。对每个节点与它的最小孩子节点比较,如果大于最小孩子节点,那么将孩子节点上移,该节点下移。直到找到不大于孩子节点的位置或者到孩子节点。将该节点值保存。
    排序思想:
    a. 使用变量index1=n-1。
    b. 数组长度为n,循环n-1次。
    c. 每次循环,构造(调整)一次最小堆,此时注意调整的数组长度为index1+1。排好序的元素不再调整。
    d. 交换第一个元素和第index1个元素,index1–。(较小元素放到后面)
    e. 直到循环结束,输出排序结果。

    void outputt(int t[], int len) // 数组输出
    {
        int i;
        for(i=0; i<len-1; i++) // 输出测试
        {
            printf("%d ", t[i]);
        }
        printf("%d\n", t[i]);
    }
    
    void heap(int t[], int len) // 调整二叉树生成堆
    {
        int i;
        int l, r;
        int min, u;
        int ti, values;
        for(i=len/2-1; i>=0; i--) // 数组下标从0开始
        {
            ti = i; // 指向i元素存放位置
            values = t[i];
            while(ti < len)
            {
                l = 2 * ti + 1;
                r = l + 1;
                u = -1;
    
                if(l < len) // 取孩子中最小者最小
                {
                    min = t[l];
                    u = l;
                }
                if(r < len && t[r] < min)
                {
                    min = t[r];
                    u = r;
                }
    
                if(u == -1) // 到达叶子节点
                    break;
    
                if(values > min)
                {
                    t[ti] = min;
                    ti = u;
                }
                else // 不大于孩子节点
                    break;
            }
            t[ti] = values; // 存放该值
        }
    }
    
    void heapSort(int t[], int len) // 进行堆排序
    {
        int tmp;
        int index1 = len - 1;
        while(index1 > 0) // 当未排序的只剩一个时,没必要再排
        {
            heap(t, index1 + 1); // 构造或调整最小堆
            tmp = t[0];
            t[0] = t[index1];
            t[index1] = tmp;
            outputt(t, 9); // 查看排序过程
            index1--;
        }
    }

    4、最小堆删除元素。每次删除第一个元素,并且把最后一个元素拿过来补充第一个元素,然后对这个新的二叉树进行调整使其满足最小堆的条件,不过此时调整仅从根节点调整即可。其实第三部分的堆排序中,只有第一次需要从最后一个非叶子节点进行调整,其他情况从根节点调整即可。最大堆的使用在最小堆的某些判断条件处更改即可。

    展开全文
  • python实现最大堆,最小堆和堆排序

    千次阅读 2019-04-13 22:35:00
    2.最小堆的实现 3.堆排序 0.什么是堆 小堆和大堆分为如下图: 堆需要满足的条件: 1. 必须是二叉树,且必须是完全二叉树 2. 各个父节点必须大于或小于左右结点, 其中最顶层的根结点必须是最大或者最小的 ...

    目录

     

    0.什么是堆

    1.最大堆的实现

    2.最小堆的实现

    3.堆排序

    0.什么是堆

    小堆和大堆分为如下图: 

    堆需要满足的条件:

    1. 必须是二叉树,且必须是完全二叉树

    2. 各个父节点必须大于或小于左右结点, 其中最顶层的根结点必须是最大或者最小的

    堆可以使用list实现,就是按照层序遍历顺序将每个节点上的值存放在数组中。父节点和子节点之间存在如下的关系:
    i 从0 开始
     parent = (i-1) // 2; left = 2*i + 1 ; right = 2*(i+1)

    1.最大堆的实现

    堆使用数组的形式表示,不需要使用指针

     

    2. 在堆中增加元素

    3,删除根节点,并重建堆结构

     

    #最大堆的实现
    class MaxHeap():
        def __init__(self, maxSize=None):
            self.maxSize = maxSize 
            self.li = [None] * maxSize
            self.count = 0
        
        def length(self):
            #求数组的长度
            return self.count 
        
        def show(self):
            if self.count <= 0:
                print('null')
            else:
                print(self.li[: self.count])
        
        def add(self, value):
            if self.count >= self.maxSize: #判断是否数组越界
                raise Exception('full')
            
            self.li[self.count] = value #将新节点增加到最后
            self._shift_up(self.count) # 递归构建大堆
            self.count += 1
        
        def _shift_up(self, index):
            #往大堆中添加元素,并保证根节点是最大的值:
            #1.增加新的值到最后一个结点,在add实现; 2.与父节点比较,如果比父节点值大,则交换
            if index > 0:
                parent = (index - 1) // 2 # 找到根节点
                if self.li[index] > self.li[parent]: #交换结点
                    self.li[index], self.li[parent] = self.li[parent], self.li[index]
                    self._shift_up(parent) #继续递归从底往上判断
                
        def extract(self):    
            #弹出最大堆的根节点,即最大值
            #1.删除根结点,将最后一个结点作为更结点 ; 2.判断根结点与左右结点的大小,交换左右结点较大的
            if not self.count:
                raise Exception('null')
            value = self.li[0] 
            self.count -= 1
            self.li[0] = self.li[self.count]  #将最后一个值变为第一个
            self._shift_down(0)
            return value
        
        def _shift_down(self, index):
            # 1.判断是否有左子节点并左大于根,左大于右;2.判断是否有右子节点,右大于根
            left = 2 * index +1
            right = 2 * index + 2
            largest = index 
            #判断条件
    # 下面2个条件包含了,判断左右结点那个大的情况。如果为3, 4, 5,:
    第一个判断条件使得largest=1,再执行第二个条件,则判断其左结点与右结点的大小
           if left < self.length() and self.li[left] > self.li[largest]:
                largest = left
            if right < self.length() and self.li[right] > self.li[largest]:
                largest = right
    
            if largest != index: # 将 两者交换
                self.li[index], self.li[largest] = self.li[largest], self.li[index]
                self._shift_down(largest)
            
    
    m = MaxHeap(10)  
    import numpy as np 
    np.random.seed(123)
    num = np.random.randint(100, size =10) #创建随机的10个数
    print(m.length())
    for i in num:
        m.add(i)
    m.show()    
    print(m.length())     
    for i in range(5):
        print(m.extract(), end=' ,') 

     

    2.最小堆的实现

    #构造最小堆 
    class MinHeap():
        def __init__(self, maxSize=None):
            self.maxSize = maxSize 
            self.array = [None] * maxSize 
            self._count = 0
        
        def length(self):
            return self._count 
        
        def show(self):
            if self._count <= 0:
                print('null')
            print(self.array[: self._count], end=', ')
        
        def add(self, value):
            #增加元素
            if self._count >= self.maxSize:
                raise Exception('The array is Full')
            self.array[self._count] = value
            self._shift_up(self._count)
            self._count += 1
        
        def _shift_up(self, index):
            #比较结点与根节点的大小, 较小的为根结点
            if index > 0:
                parent = (index - 1) // 2
                if self.array[parent] > self.array[index]:
                    self.array[parent], self.array[index] = self.array[index], self.array[parent]
                    self._shift_up(parent)
        
        def extract(self):           
            #获取最小值,并更新数组
            if self._count <= 0:
                raise Exception('The array is Empty')
            value = self.array[0]
            self._count -= 1 #更新数组的长度
            self.array[0] = self.array[self._count] #将最后一个结点放在前面
            self._shift_down(0)
            
            return value 
                 
        def _shift_down(self, index):  
            #此时index 是根结点
            if index < self._count:
                left = 2 * index + 1
                right = 2 * index + 2
                #判断左右结点是否越界,是否小于根结点,如果是这交换
                if left < self._count and right < self._count and self.array[left] < self.array[index] and self.array[left] < self.array[right]:
                    self.array[index], self.array[left] = self.array[left], self.array[index] #交换得到较小的值
                    self._shift_down(left)
                elif left < self._count and right < self._count and self.array[right] < self.array[left] and self.array[right] < self.array[index]:
                    self.array[right], self.array[index] = self.array[index], self.array[right]
                    self._shift_down(right)
                
                #特殊情况: 如果只有做叶子结点
                if left < self._count and right > self._count and self.array[left] < self.array[index]:
                    self.array[left], self.array[index] = self.array[index], self.array[left]
                    self._shift_down(left)
    
    mi = MinHeap(10)
    print()
    print('-------小顶堆----------')
    for i in num:
        mi.add(i)
    mi.show()
    print(mi.length())
    for _ in range(len(num)):
        print(mi.extract(), end=', ')
    print()
    print(mi.length())

    参考:https://blog.csdn.net/qq_23869697/article/details/82735088

    https://python-data-structures-and-algorithms.readthedocs.io/zh/latest/15_%E5%A0%86%E4%B8%8E%E5%A0%86%E6%8E%92%E5%BA%8F/heap_and_heapsort/#_4

     

    3.堆排序

    def maxHeapfy(alist, length, parent):
        left = 2 * parent + 1
        right = 2 * parent + 2
        largest = parent
        if left < length and alist[left] > alist[largest]:
            largest = left
        if right < length and alist[right] > alist[largest]:
            largest = right
        if largest != parent:
            alist[largest], alist[parent] = alist[parent], alist[largest]
            maxHeapfy(alist, length, largest)  # 递归构建
    
    def buildMaxHeap(alist):  # 构建最大堆
        n = len(alist)
        lastParent = (n-1) // 2
        for i in range(lastParent, -1, -1):
            maxHeapfy(alist, n, i)
    
    def heapSort(alist):
        buildMaxHeap(alist)
        n = len(alist)
        for i in range(n-1, -1, -1):
            alist[0], alist[i] = alist[i], alist[0]  # 将最大值放在最后面
            maxHeapfy(alist, i, 0)
        return alist
    
    a = [30,50,57,77,62,78,94,80,84]
    print(a)
    print(heapSort(a))
    alist = [2, 4, 1, 2, 5, 58, 45, 24, 67]
    print(heapSort(alist))
    b = [random.randint(1,1000) for i in range(1000)]
    print(b)
    print(heapSort(b))

     

    项目推荐:

    2000多G的计算机各行业电子资源分享(持续更新)

    2020年微信小程序全栈项目之喵喵交友【附课件和源码】

    Spring Boot开发小而美的个人博客【附课件和源码】

    Java微服务实战296集大型视频-谷粒商城【附代码和课件】

    Java开发微服务畅购商城实战【全357集大项目】-附代码和课件

    最全最详细数据结构与算法视频-【附课件和源码】

    在这里插入图片描述

     

    展开全文
  • C++ 最小堆

    千次阅读 2019-03-14 12:52:23
    // 对最小堆的各种操作 // 最小堆:完全二叉树,可以采用顺序存储结构 #include &lt;iostream&gt; #include &lt;stack&gt; const int DefaultSize = 100; template &lt;class T&gt; ...
    //  对最小堆的各种操作
    //  最小堆:完全二叉树,可以采用顺序存储结构
    
    #include <iostream>
    #include <stack>
    
    const int DefaultSize = 100;
    
    template <class T>
    class MinHeap{
    public:
        MinHeap(int sz = DefaultSize);
        MinHeap(T arr[], int n);
        ~MinHeap(){delete []heap;}
        bool Insert(const T &x); // 插入
        bool RemoveMin(); // 删除
        bool isEmpty()const; // 是否为空
        bool isFull()const; // 是否已满
        void PreOrder(); // 前序遍历完全二叉树
    private:
        T *heap; // 动态数组存储最小堆
        int CurrentSize; // 目前最小堆的结点数
        void ShiftDown(int start, int m); // 下滑
        void ShiftUp(int start); // 上浮
    };
    
    // 构造函数
    template <class T>
    MinHeap<T>::MinHeap(int sz) {
        heap = new T[sz]; // 创建堆空间
        CurrentSize = 0;
    }
    
    // 构造函数
    template <class T>
    MinHeap<T>::MinHeap(T arr[], int n) {
        // 为什么求最后非叶要CurrentSize减去2,再除以2,而不是减去1,再除以2
        // 因为最后一个数组下标是CurrentSize-1,又因为:左结点j = 2 * i +
        //  1,知道j,想求i。可知是:i = (j - 1) / 2;所以,就出现了
        // CurrentPos = (CurrentSize - 2) / 2
        heap = new T[DefaultSize]; // 创建堆空间
        CurrentSize = n; // 当前堆大小
        for(int i = 0; i < n; i++)
            heap[i] = arr[i];
        int CurrentPos = (CurrentSize - 2) / 2; // 最后非叶
        while(CurrentPos >= 0) {
            // 从下到上逐渐扩大,形成堆
            ShiftDown(CurrentPos, CurrentSize-1);
            // 到CurrentSize-1为止
            CurrentPos--;
        }
    }
    
    // 向下调整
    template <class T>
    void MinHeap<T>::ShiftDown(int start, int m) {
        int i = start, j = 2 * i + 1; // j是i的左子女
        
        T temp = heap[i];
        while(j <= m) {
            if(j < m && heap[j] > heap[j+1])
                j++; // 选两个子女中较小者
            if(temp <= heap[j])
                break;
            else {
                heap[i] = heap[j];
                i = j;
                j = 2 * j + 1;
            }
        }
        heap[i] = temp;
    }
    
    // 向上调整
    template <class T>
    void MinHeap<T>::ShiftUp(int start) {
        // 从start开始,直到0或者当前值大于双亲结点的值时,调整堆
        int j = start, i = (j-1)/2; // i是j的双亲
        
        T temp = heap[j];
        while(j > 0) {
            if(heap[i] <= temp)
                break;
            else {
                heap[j] = heap[i];
                j = i;
                i = (j - 1) / 2;
            }
        }
        heap[j] = temp;
    }
    
    // 堆插入
    template <class T>
    bool MinHeap<T>::Insert(const T &x) {
        // 在堆中插入新元素x
        if(CurrentSize == DefaultSize) { // 堆满
            std::cout << "堆已满!\n";
            return false;
        }
        heap[CurrentSize] = x; // 插在表尾
        ShiftUp(CurrentSize); // 向上调整
        CurrentSize++;
        return true;
    }
    
    // 堆删除
    template <class T>
    bool MinHeap<T>::RemoveMin() {
        int x;
        
        if(!CurrentSize) {
            std::cout << "堆已空!\n";
            return false;
        }
        x = heap[0]; // 最小元素出列
        heap[0] = heap[CurrentSize-1]; // 用最后一个元素填补
        CurrentSize--;
        ShiftDown(0, CurrentSize-1); // 从0位置开始向下调整
        return true;
    }
    
    // 判断堆是否已空
    template <class T>
    bool MinHeap<T>::isEmpty()const {
        if(!CurrentSize)
            return true;
        return false;
    }
    
    // 判断堆是否已满
    template <class T>
    bool MinHeap<T>::isFull()const {
        if(CurrentSize == DefaultSize)
            return true;
        return false;
    }
    
    // 前序遍历
    template <class T>
    void MinHeap<T>::PreOrder() {
        std::stack<int> s;
        int i;
        
        i = 0;
        while(i < CurrentSize || !s.empty()) {
            while(i < CurrentSize) {
                std::cout << heap[i] << " ";
                s.push(i);
                i = 2 * i + 1;
            }
            if(!s.empty()) {
                i = s.top();
                s.pop();
                i = 2 * i + 2;
            }
        }
    }
    
    int main(int argc, const char * argv[]) {
        int finished, choose, x, len;
        int arr[] = {9, 17, 65, 23, 45, 78, 87, 53};
        
        len = sizeof(arr) / sizeof(arr[0]);
        finished = 0;
        MinHeap<int> h = MinHeap<int>(arr, len);
        
        while(!finished) {
            std::cout << "\n*************菜单*************\n";
            std::cout << "1:往最小堆中插入一个值:\n";
            std::cout << "2:删除最小堆中的最小值\n";
            std::cout << "3:判断最小堆是否为空\n";
            std::cout << "4:判断最小堆是否已满\n";
            std::cout << "5:前序遍历最小堆\n";
            std::cout << "6:退出\n";
            std::cout << "请输入你的选择[1-6]:";
            std::cin >> choose;
            switch(choose) {
                case 1:
                    std::cout << "请输入要插入的值:";
                    std::cin >> x;
                    h.Insert(x);
                    break;
                case 2:
                    h.RemoveMin(); // 删除最小值
                    break;
                case 3:
                    if(h.isEmpty())
                        std::cout << "最小堆为空!\n";
                    else
                        std::cout << "最小堆不为空!\n";
                    break;
                case 4:
                    if(h.isFull())
                        std::cout << "最小堆已满\n";
                    else
                        std::cout << "最小堆还没满!\n";
                    break;
                case 5:
                    std::cout << "最小堆的数据为:\n";
                    h.PreOrder();
                    std::cout << std::endl;
                    break;
                case 6:
                    finished = 1;
                    break;
                default:
                    std::cout << "选择输入错误,请重新输入!\n";
            } // switch
        } // while
        return 0;
    }
    

     

    展开全文
  • C++ 实现最大堆和最小堆的构造过程
  • 最大堆、最小堆详解

    千次阅读 2018-10-16 15:05:42
    最大堆、最小堆详解 Overview 最大堆和最小堆是二叉堆的两种形式。二叉堆(binary heap)是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父节点总是保持固定的序关系于任何一个子节点的...
  • 最小堆 最小堆数据结构也是一棵完全二叉树(叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树)。 因为完全二叉树的性质,因此我们用数组来存储树的节点,从上到...
  • 最小堆排序

    2018-06-14 14:57:28
    堆排序分为最大堆排序和最小堆排序,今天我们来说一说最小堆排序。最小堆是完全二叉树的一种,它的特征是每个父亲结点都小于其两个孩子结点,至于两个孩子结点的大小,不做要求。 最小堆排序的核心函数是筛选函数,...
  • 深入理解堆(最大堆,最小堆及堆排序)

    万次阅读 多人点赞 2018-09-17 20:31:34
    基本概念: 1、完全二叉树:若二叉树的深度为h,则除第h...2、堆中的某个结点的值总是大于等于(最大堆)或小于等于(最小堆)其孩子结点的值。 3、堆中每个结点的子树都是堆树。 堆的操作 假设原始数据为a[]...
  • 最小堆的建立

    千次阅读 2015-06-05 17:15:00
    最小堆的建立
  • 最小堆建立

    千次阅读 2016-03-07 22:49:30
    题目来源:http://dsalgo.openjudge.cn/201409week5/2/最小堆建立题目:实现最小堆两个功能: 1、增加一个元素 2、输出并删除最小堆中的最小的数 输入: 第一行输入一个整数t,代表测试数据的组数。 对于每组...
  • 最小堆排序: 1 首先利用最小堆的这种数据结构的特点,子节点不小于父节点的特性,最小堆构建后,根节点就是最小值 2 构建最小堆:子节点中最小的和父节点互换,然后对子节点的子树递归构建最小堆 3 最小堆构建...
  • 堆树(最大堆、最小堆)详解

    万次阅读 多人点赞 2016-03-16 13:30:58
    一、堆树的定义 堆树的定义如下: (1)堆树是一颗完全二叉树... 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示,左边为最大堆,右边为最小堆。 二、堆树的操作 以最大堆为例进行讲解
  • Java实现最小堆

    2020-08-01 17:01:37
    堆,其实是一种优先队列,分为最大堆和最小堆。在最小堆中,它首先是一颗完全二叉树,并且根节点的值,要比左右孩子的值都要小,同时,左右子树也是最小堆。本文包含堆的操作如下: (1)插入一个节点 (2)删除堆...
  • 最小堆 构建、插入、删除的过程图解

    万次阅读 多人点赞 2016-05-21 00:47:02
     最小堆是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子的值。本文以图解的方式,说明 最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后,最大堆与此类似。 2.最小堆示例 3.最小堆的构建  ...
  • C++实现最大堆和最小堆

    千次阅读 2018-08-19 20:47:17
    堆 堆数据结构是一种数组对象,... 最小堆: 任一结点的关键码均小于等于它的左右孩子的关键码,其中堆顶的元素最小。(任一路径中的元素升序排列) 已知父节点: 左孩子节点 = 2*父节点+1 右孩子节点 = ...
  • 最小堆建立和堆排序

    千次阅读 2018-10-03 10:34:17
    堆树的定义: ... 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示,左边为最小堆,右边为最大堆。   数组与堆 无序数组转化成原始的二叉堆: 4 5 3 ...
  • 数据结构 堆树(最大堆、最小堆

    千次阅读 2019-01-09 15:36:10
    一、堆树的定义 ...当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆,也称小根堆。 如下图所示,上边为最大堆,下边为最小堆。 二、堆树的操作 下面以最大堆为例进行讲解,最小堆同理。 2.1...
  • 堆排序(最小堆)C++

    千次阅读 2018-10-01 15:58:36
    堆分为大根堆(最大堆)和小根堆(最小堆),堆排序就是二叉堆的升级版,实际上是一棵完全二叉树 不同的是这棵二叉树里每个节点保证父节点都小于孩子节点 最后进行堆排序,将堆顶最小的节点(第一个)与最后一个...
  • 最小堆解决Top K问题

    千次阅读 2016-11-18 17:11:51
    问题描述:有一组数据n个,要求取出这组...从n开始循环数组的剩余元素,如果元素(a)比最小堆的根节点大,将a设置成最小堆的根节点,并让堆保持最小堆的特性。 循环完成后,最小堆中的所有元素就是需要找的最大的n个元素
  • 堆是一种经过排序的完全二叉树,其中任一非终端节点...而最大-最小堆集结了最大堆和最小堆的优点,这也是其名字的由来。 最大-最小堆是最大层和最小层交替出现的二叉树,即最大层结点的儿子属于最小层,最小层结点的儿
  • python实现最小堆

    千次阅读 2019-04-17 23:21:02
    最小堆特点: 类似一颗完全二叉树 二叉树中所有的父节点的值都小于其子节点; 根节点的值必定是所有节点中最小的。 父节点值不大于子节点且根节点值最小称为最小堆,反之称为最大堆。最大堆和最小堆没有本质上的...
  • 删除最小堆的最小值

    2015-06-05 18:05:12
    删除最小堆的最小值
  • 最小堆。最大堆。

    万次阅读 2012-11-08 23:00:06
    最大堆和最小堆是二叉堆的两种形式。 最大堆:根结点的键值是所有堆结点键值中最大者,且每个结点的值都比其孩子的值大。 最小堆:根结点的键值是所有堆结点键值中最小者,且每个结点的值都比其孩子的值小。 ...
  • 最小堆最大堆算法JAVA

    万次阅读 2017-09-11 21:38:34
    最小堆又叫小顶堆,小顶堆是一棵完全二叉树,满足小顶堆的条件是每个孩子节点的值都大于父节点。大顶堆则相反。     /** * 最小堆 * @author dwl * */ public class MinHeap { //使用数组存储堆中的数据 ...
  • 最大堆和最小堆的实现 这一讲讲的还是堆,因此将它归入到堆(一)中。这一篇博客的目的非常简单,就是补充一下,堆的实现代码。Heap是抽象类,它有两个子类,MaxHeap和MinHeap。至于它们的function,我不再赘述了,...
  • 二叉堆二叉堆是一颗完全二叉树,该树中的某个节点的值总是不大于(不小于)其左右子节点的值,包括最小堆和最大堆。可以通过下图理解,为什么会使用数组来保存呢?因为利用完全二叉树的性质,我们可以...
  • 最大堆/最小堆

    2013-07-23 10:02:00
    1.堆定义 堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)...而最大-最小堆集结了最大堆和最小堆的优点,这也是其名字的由来。 最大-最小堆是最大层和最小层交替出现的二叉树,即最大
  • 最大堆最小堆的建立

    2017-05-22 11:41:10
    堆是一种数据结构,它是一颗完全二叉树,最大堆和最小堆是二叉堆的两种形式。 最大堆:每个父亲结点的键值都大于孩子结点 最小堆:每个父亲结点的键值都小于孩子结点 下面看一下我的实现方式↓ #pragma ...
  • 二叉堆(最小堆, 最大堆)介绍与实现

    千次阅读 2019-06-13 11:53:16
    二叉堆是一种特殊的二叉树, 它总是保证一棵树的最小元素(最小堆)或者最大元素(最大堆)处于树根上, 常见的应用场景就是用于构建优先队列, 在jdk中Doug Lea所实现的ScheduledThreadPoolExecutor中就是用到了最小堆;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 267,214
精华内容 106,885
关键字:

最小堆