精华内容
下载资源
问答
  • 2018-10-22 23:54:55

    堆可以用数组表示,其中a[0]放入一个最小值,哨兵牌

     插入操作放在数组最后,然后如果这个点的父节点大于这个插入的值

    那么把子节点的值用父节点替代,父节点继续向上比较,移动到合适位置,在赋相应的值

    pop操作,pop的值是a[1], 从第一个节点开始调整后面的值PercDown(H, 1)

    给定一个乱序的数组,如何直接把他变成一个堆

    /* 从最后一个结点的父节点开始,到根结点1 */
        for (i = H->Size / 2; i>0; i--)
            PercDown(H, i);

    #include<stdio.h>
    #include<stdlib.h>
    #define N  10005
    typedef int ElementType;
    typedef struct HNode *Heap; /* 堆的类型定义 */
    struct HNode {
    	ElementType *Data; /* 存储元素的数组 */
    	int Size;          /* 堆中当前元素个数 */
    	int Capacity;      /* 堆的最大容量 */
    };
    typedef Heap MaxHeap; /* 最大堆 */
    typedef Heap MinHeap; /* 最小堆 */
    
    #define MAXDATA 1000  /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */
    #define MINDATA -1000
    
    
    
    MinHeap CreateMinHeap(int MaxSize)
    { /* 创建容量为MaxSize的空的最小堆 */
    
    	MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    	H->Data = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType));
    	H->Size = 0;
    	H->Capacity = MaxSize;
    	H->Data[0] = MINDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/
    
    	return H;
    }
    
    
    bool IsFull(MinHeap H)
    {
    	return (H->Size == H->Capacity);
    }
    
    
    
    bool Insert(MinHeap H, ElementType X)
    { /* 将元素X插入最小堆H,其中H->Data[0]已经定义为哨兵 */
    	int i;
    	if (IsFull(H)) {
    		printf("最小堆已满");
    		return false;
    	}
    	i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
    	for (; H->Data[i / 2] > X; i /= 2)
    		H->Data[i] = H->Data[i / 2]; /* 上滤X */
    	H->Data[i] = X; /* 将X插入 */
    	return true;
    }
    
    #define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
    
    
    
    bool IsEmpty(MinHeap H)
    {
    	return (H->Size == 0);
    }
    
    
    
    ElementType Deletemin(MinHeap H)
    {
    	/* 从最小堆H中取出键值为最小的元素,并删除一个结点 */
    	int Parent, Child;
    	ElementType MinItem, X;
    
    	if (IsEmpty(H)) {
    		printf("最小堆已为空");
    		return ERROR;
    	}
    
    	MinItem = H->Data[1]; /* 取出根结点存放的最小值 */
    						  /* 用最小堆中最后一个元素从根结点开始向上过滤下层结点 */
    	X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
    	for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
    		Child = Parent * 2;
    		if ((Child != H->Size) && (H->Data[Child]>H->Data[Child + 1]))
    			Child++;  /* Child指向左右子结点的较小者 */
    		if (X <= H->Data[Child]) break; /* 找到了合适位置 */
    		else  /* 下滤X */
    			H->Data[Parent] = H->Data[Child];
    	}
    	H->Data[Parent] = X;
    
    	return MinItem;
    }
    
    
    /*----------- 建造最小堆 -----------*/
    void PercDown(MinHeap H, int p)
    { /* 下滤:将H中以H->Data[p]为根的子堆调整为最小堆 */
    	int Parent, Child;
    	ElementType X;
    	X = H->Data[p]; /* 取出根结点存放的值 */
    	for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {
    		Child = Parent * 2;
    		if ((Child != H->Size) && (H->Data[Child]>H->Data[Child + 1]))
    			Child++;  /* Child指向左右子结点的较小者 */
    		if (X <= H->Data[Child]) break; /* 找到了合适位置 */
    		else  /* 下滤X */
    			H->Data[Parent] = H->Data[Child];
    	}
    	H->Data[Parent] = X;
    }
    
    void BuildHeap(MinHeap H)
    { /* 调整H->Data[]中的元素,使满足最小堆的有序性  */
      /* 这里假设所有H->Size个元素已经存在H->Data[]中 */
    	int i;
    	/* 从最后一个结点的父节点开始,到根结点1 */
    	for (i = H->Size / 2; i>0; i--)
    		PercDown(H, i);
    }
    
    int main()
    {
    	int a[N], b[N];
    	int n;
    	scanf_s("%d", &n);
    	for (int i = 0; i < n; i++)
    	{
    		scanf_s("%d", &a[i]);
    	}
    	for (int i = 0; i < n; i++)
    	{
    		scanf_s("%d", &b[i]);
    	}
    	MinHeap H = CreateMinHeap(N);
    	int k = 1;
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j < n; j++)
    		{
    			H->Data[k] = a[i] + b[j];
    			k++;
    		}
    	}
    	H->Size = n*n;
    	BuildHeap(H);
    	int ans = 0;
    	for (int i = 0; i < n; i++)
    	{
    		ans += Deletemin(H);
    	}
    	printf("%d\n", ans);
    
    }

     

    更多相关内容
  • 代码c++ 最大堆最小堆

    2013-01-03 09:40:14
    最大堆最小堆 问题的提出 给定k个排好序的序列S1,S2…,Sk,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优...
  • 主要介绍了C语言实现基于最大堆最小堆的堆排序算法示例,分别是基于最大堆的升序排序和基于最小堆的降序排序实例,需要的朋友可以参考下
  • 最大堆最小堆的实现(C语言)

    千次阅读 2019-08-05 16:30:33
    是特殊的队列,从中取元素是按照元素的优先级大小,而不是元素进入队列的先后顺序。因此,也通常被称为“优先队列”。 的最常用结构是用二叉树表示,不特指的话,他是一棵完全二叉树。因此通常不必用指针,...

    ----------------

    该篇文章经提醒有一些错误,暂时没有时间修改,请勿参考。

    该篇文章经提醒有一些错误,暂时没有时间修改,请勿参考。

    ----------------

    堆是特殊的队列,从堆中取元素是按照元素的优先级大小,而不是元素进入队列的先后顺序。因此,堆也通常被称为“优先队列”。

    堆的最常用结构是用二叉树表示,不特指的话,他是一棵完全二叉树。因此通常不必用指针,而是用数组来实现堆的存储。我们

    知道,完全二叉树用数组来表示,就相当于把全完二叉树的层序遍历依次存入数组中,知道最后一个节点。

    需要注意的是,所用的数组的起点为1,而不是0。这样的目的是很容易能够从父节点(i)找到子节点[ 2i ] [ 2i+1 ],反过来也很容易从子节点(j)找到父节点[ j/2 ]。 

    堆的特性:

    用数组来表示完全二叉树是堆的第一特性:堆的结构特性

    任一节点的值与其子节点的值是相关的:部分有序性

    相关性的不同决定了两种不同的基本堆:最大堆(MaxHeap)(任一节点大于等于其子节点)和最小堆(MinHeap)(任一节点小于等于其子节点)。注意,兄弟节点之间没有约束关系。

    当我们需要小键值优先时,使用最小堆;需要大键值优先时,使用最大堆。

    首先来看一下堆的一般结构体实现:

    typedef struct HNode * heap;//结构体指针
    struct HNode{
        ElementType *Data;//表示堆的数组 大小要在用户输入的元素个数上+1
        int Size;//数组里已有的元素(不包含a[0]) 
        int Capacity; //数组的数量上限
    };
    typedef heap MaxHeap; //定义一个最大堆
    typedef heap MinHeap; //定义一个最小堆

    创建:

    //mheap表示maxHeap或者minHeap
    mHeap creatMHeap(int size){
        mHeap heap = (mHeap)malloc(sizeof(struct Hnode));
        heap->data = (int*)malloc(sizeof(int)*(size+1));//从a[1]开始保存数 所以数组数量要+1
        heap->Size = 0;
        heap->Capacity=size;
        heap->data[0] = MAXData OR MINDATA;//岗哨 稍后会提到
        return heap;
    }

    接下来用代码来表示最大堆和最小堆的相关操作:

    最大堆(MaxHeap):

    插入:

    从新增的最后一个节点的父节点开始,用要插入的元素向下过滤上层节点(比该元素小的下移)。

    bool insertToHeap(maxHeap heap, int x){
        //查看是否已经满了
        if (heap->Size == heap->Capacity) {
            return false;
        }
        int i = ++heap->Size;//新增的节点位置
        for (; heap->data[i/2]<x; i/=2) {
    //此处的判断 如果向上到了a[1]还没停止的话 需要让其就停在a[1]处 所以要在a[0]的位置放置一个"岗哨"
    //这个岗哨对于最大堆来说要放入一个 比数组中所有数都大的数 这样在比较a[0]和x时 a[0]>x 循环就会停下来
            heap->data[i] = heap->data[i/2];
        }
        heap->data[i] = x;
        return true;
    }

    删除:

    从根节点开始,用最大堆中的最后一个元素向上过滤下层节点(比该元素大的上移)。

    int deleteHeap(maxHeap heap){
        //判断是否空
        if (heap->Size==0) {
            return false;
        }
        int top = heap->data[1];//堆顶元素(最大)
        int last = heap->Size--;//取出数组最后一个元素
        int parent = 1;
        int child;
        for (; parent*2<=heap->Size; parent=child) {
            child = 2*parent;//左子节点
            //查找是否有右子节点 并且 右子节点的元素大于左子节点
            if (child!=heap->Size && heap->data[child]<heap->data[child+1]) {
                child++;//右子节点
                if (last<heap->data[child]) {
                    heap->data[parent] = heap->data[child];
                }else{//找到了位置
                    break;
                }
            }
        }
        heap->data[parent] = last;
        return top;
    }

    构造:

    虽说构造一个最大堆时只要把一个个元素按照插入方法插入到数组中即可完成。但是其时间复杂度是(O(N log N))。我们有一种更简单的方式,使得时间复杂度下降到O(N)。

    1.将输入的元素按顺序放入完全二叉树(数组)中。

    2.调整各个节点的位置,满足最大堆的有序性。

    调整的过程就是从最后一个父节点开始倒序到根节点,逐一向下进行过滤操作(同删除的向下过滤一样,不过过滤元素就是父节点本身的元素)。

    void percDown(maxHeap heap, int n){
        int top,parent,child;
        top = heap->data[n];//取出父节点元素
        //向下过滤
        for (parent = n; parent*2<heap->Size; parent=child) {
            child = 2*parent;
            if (child!=heap->Size && heap->data[child]<heap->data[child+1]) {
                child++;
                if (heap->data[child]<=n) {
                    break;
                }else
                    heap->data[child] = heap->data[parent];
            }
        }
        heap->data[parent] = top;
    }
    
    void buildMaxHeap(maxHeap heap){
        for (int i=heap->Size/2; i>0; i--) {//从最后一个父节点开始
            percDown(heap, i);
        }
    }

    最小堆(MaxHeap):

    由于最大堆和最小堆只是元素的顺序位置不同,具体的操作只是细节判断的修改,就只提下插入和删除操作把:

    插入:

    
    bool insertMinHeap(minHeap heap, int x){
        //判断是否满了
        if (heap->Size == heap->Capacity){
            return false;
        }
        int p = ++heap->Size;
        for (; heap->data[p/2]<x; p/=2) {
    //这里是最小堆  所以在a[0]位置的岗哨保存了比数组中所有元素都小的元素
            heap->data[p] = heap->data[p/2];
        }
        heap->data[p] = x;
        return true;
    }

    删除:

    int deleteFromMinHeap(minHeap heap){
        int top = heap->data[1];
        int last = heap->data[heap->Size--];
        int parent,child;
        for (parent = 1; parent*2<heap->Size; parent=child) {
            child = parent*2;
                //注意这里是存在右子节点 并且 右子节点比左子节点小    
            if (child!=heap->Size && heap->data[child] > heap->data[child+1]) {
                child++;
                //如果比右子节点还小
                if (heap->data[child]>last) {
                    break;
                }else{//下滤
                    heap->data[parent] = heap->data[child];
                }
            }
        }
        heap->data[parent] = last;
        return top;
    }

    展开全文
  • 数据结构课程设计 堆算法 最大堆 最小堆 相关堆算法
  • C++ 构建最小堆最大堆

    千次阅读 2020-08-10 08:31:18
    C++ 实现最大堆最小堆的构造过程
    • 堆的属性
    1. 完全二叉树
    2. 每个节点的值都大于(最大堆)或都小于(最小堆)子节点的值

    堆只是一种数据的组织形式,存储结构可以用数组,在构建堆的过程中,可以使用完全二叉树的性质求父子节点的下标。

    父节点的下标 = 向下取整 ( (子节点下标 - 1) /  2)
    
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <cmath>
    void minheap();
    void maxheap();
    using namespace std;
    int arr[8] = { 53,17,78,9,45,65,87,23 };
    int *a = new int[8];//保存小根堆
    int index = 0;
    int main()
    {
        minheap();
        cout << "建立的最小堆为:" << endl;
        for (int i = 0; i < 8; i++)
        {
            cout << a[i] <<" ";
        }
        system("pause");
    }
    
    void maxheap() {
      while(index < 8) {
        a[index] = arr[index];
        if (index != 0) {
          int son_index = index;
          int par_index = floor((son_index - 1) / 2);
          while(a[par_index] < a[son_index]) {
            int tmp = a[par_index];
            a[par_index] = a[son_index];
            a[son_index] = tmp;
            son_index = par_index;
            par_index = floor((par_index - 1) / 2);
          }
        }
        index ++;
      }
    }
    void minheap()
    {
      while (index < 8) {
        a[index] = arr[index];
        if (index != 0) {
          int son_index = index;
          int par_index = floor((son_index - 1) / 2);
          while (a[par_index] > a[son_index]) {//小根堆:父节点大的话需要交换
              int temp = a[par_index];//交换
              a[par_index] = a[son_index];
              a[son_index] = temp;
              son_index = par_index;//迭代看之前的是否需要调整
              par_index = floor((son_index - 1) / 2);
          }
        }
        index ++;
      }
    }
    
    展开全文
  • python 中的最大堆最小堆(heapq库)

    千次阅读 2022-04-11 20:09:55
    python heapq库 最大堆最小堆

    目录

    首先来看一下什么是最大堆和最小堆?

    python heapq库中的一些常用方法

    小试牛刀


    首先来看一下什么是最大堆和最小堆?

    最大堆:一种经过排序的完全二叉树,其中任意非终端节点数值均不小于其左子节点和右子节点的值。如果一颗二叉树满足最小堆的要求,那么,堆顶(根节点)也就是整个序列的最大元素。

    最小堆:也是一种经过排序的完全二叉树,其中任意非终端节点数值均不大于其左子节点和右子节点的值。如果一棵二叉树满足最小堆的要求,那么,堆顶(根节点)也就是整个序列的最小元素。

    python heapq库中的一些常用方法

    注意:python中的heapq库只有最小堆,没有最大堆,当使用最大堆时,可以在插入元素时将元素取反,弹出是也取反,一些常用操作如下:

    import heapq
    # [2,0,4,1]
    
    # 1.创建堆
    # 方法一:定义一个空列表,然后使用heapq.heqppush(item)函数把元素加入到堆中
    item = 2
    heap = []
    heapq.heappush(heap,item)
    # 方法二:使用heapq.heapify(list)将列表转换为堆结构
    heap = [2,0,4,1]
    heapq.heapify(heap)
    
    # 2.heapq.heappush() 添加新元素 num
    num = 3
    heapq.heappush(heap,num)
    
    # 3.heapq.heappop() 删除并返回堆顶元素
    heapq.heappop(heap)
    
    # 4.heapq.heappushpop() 比较添加元素num与堆顶元素的大小:如果num>堆顶元素,删除并返回堆顶元素,然后添加新元素num;如果num<堆顶元素,返回num,原堆不变
    # 其实也就等价于 添加新元素num,然后删除并返回堆顶元素
    num = 0
    heapq.heappushpop(heap,num)
    
    # 5.heapq.heapreplace() 删除并返回堆顶元素,然后添加新元素num
    num = 5
    heapq.heapreplace(heap,num)
    
    # 6. heapq.merge() 合并多个排序后的序列成一个排序后的序列, 返回排序后的值的迭代器。
    heap1 = [1,3,5,7]
    heap2 = [2,4,6,8]
    heap = heapq.merge(heap1,heap2)
    print(list(heap))
    
    # 7.heapq.nsmallest() 查询堆中的最小n个元素
    n = 3
    heap = [1,3,5,7,2,4,6,8]
    print(heapq.nsmallest(n,heap)) # [1,2,3]
    
    # 8.heapq.nlargest() 查询堆中的最大n个元素
    n = 3
    heap = [1,3,5,7,2,4,6,8]
    print(heapq.nlargest(n,heap)) # [8,7,6]

    小试牛刀

    题目1:剑指 Offer 40. 最小的k个数

    # 最大堆解法,参考题解:https://www.bilibili.com/video/BV1To4y1d7cW/
    import heapq
    class Solution:
        def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
            if k == 0:
                return []
            # python中只有最小堆,没有最大堆
            # 将所有元素取反,弹出的时候也取反
            heap = [-x for x in arr[0:k]]
            heapq.heapify(heap)
            for x in arr[k:]:
                if -x > heap[0]:
                    heapq.heapreplace(heap,-x)
            return [-x for x in heap]

    题目2:剑指 Offer 41. 数据流中的中位数

    # 最大堆最小堆解法,参考题解:https://www.bilibili.com/video/BV1J5411J7yj/
    import heapq
    class MedianFinder:
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.maxHeap = [] # 最大堆保存的是最小的n/2个数
            self.minHeap = [] # 最小堆保存的是最大的n/2个数
    
        def addNum(self, num: int) -> None:
            # 若两堆的数目相等,就让minHeap的元素个数+1
            # 具体做法分为两步 1.将新元素加入maxHeap 2.将maxHeap的堆顶元素加入minHeap
            if len(self.maxHeap)==len(self.minHeap):
                heapq.heappush(self.minHeap,-heapq.heappushpop(self.maxHeap,-num))
            else:
                heapq.heappush(self.maxHeap,-heapq.heappushpop(self.minHeap,num))
                
        def findMedian(self) -> float:
            if len(self.maxHeap)==len(self.minHeap):
                return (self.minHeap[0]-self.maxHeap[0])/2.0
            else:
                return self.minHeap[0]

    展开全文
  • STL中优先队列(堆)和自定义最大堆最小堆引言最大堆的一个例子最小堆的一个例子 引言 在算法实践中,有的算法要求不停地插入或移除最大或最小值。若用线性比较,则时间复杂度为O(n2n^2n2)。这时候,若用优先队列,...
  • 最大堆最小堆类似,以下以最小堆为例进行讲解。 最小堆是满足以下条件的数据结构: 它是一棵完全二叉树 所有父节点的值小于或等于两个子节点的值 1.2 什么是完全二叉树 除了最后一层之外的其他每一层都被完全...
  • 最大堆最小堆详解

    千次阅读 2018-10-16 15:05:42
    最大堆最小堆详解 Overview 最大堆和最小堆是二叉堆的两种形式。...文章目录最大堆最小堆详解Overview一、二叉堆二、最大堆最小堆详解(以最大堆为例)由上至下的下沉建堆操作(以最大堆为例)...
  • 最大堆最小堆操作——python

    千次阅读 2019-05-06 16:12:21
    刚讲完的一系列基本内容,把涉及的知识点整理下,看课本81-88页自行对照复习。 heap,通常是一个可以被看做一棵树的数组对象。 的性质:(1)是轶可完全二叉树;(2)某个节点的值总是大于或小于子节点 相关...
  • 创建的方式有两种,一种是一边插入结点,一边调用的插入方法调整,这样的时间复杂度就是 O(NlogN),而第二种方式就把时间复杂度缩减到了O(N),它是采用先把结点插入好了,然后再来调整,并不是一边插入一边...
  • 两个堆,一个最大堆来实现储存比中位数m小或者相等的值,一个最小堆来储存比m大或者相等的值,当有新的数进来,根据与m的关系,大于m的值放到最小堆,小于m的值放到最大堆。当两个堆的元素个数差值大于1时,就表明,...
  • c++实现最大堆最小堆

    千次阅读 2020-03-12 02:44:55
    每个结点的值都小于或等于其左右孩子结点的值,叫做最小堆。 一、建堆 vector<int> nums = {9, 6, 2, 4, 7, 0, 1, 8, 3, 5}; 1、如果使用nums构建最大堆: make_heap(nums.begin(), nu...
  • 最大堆最小堆C++实现

    千次阅读 2016-06-23 21:45:23
    最近学习了最大堆最小堆数据结构,这个并不难懂,但在编程、编写学习笔记时,发现有不少错误、理解不深刻,有比较多的细节需要注意的,特别是孩子节点的访问条件、几个节点之间的比较出了不少错误,但经过一番努力...
  • 最大堆最小堆的建立

    2017-05-22 11:41:10
    最大堆:每个父亲结点的键值都大于孩子结点 最小堆:每个父亲结点的键值都小于孩子结点 下面看一下我的实现方式↓ #pragma once #include using namespace std; template struct Great { bool ...
  • C++之最小堆最大堆

    千次阅读 2019-07-03 20:23:04
    #include<queue> #include<vector> std::priority_queue<... // 构造一个默认最大堆 std::priority_queue<int, std::vector<int>, std::greater<int> > small_heap; //构造一个...
  • 最大堆和最小堆的实现 这一讲讲的还是堆,因此将它归入到堆(一)中。这一篇博客的目的非常简单,就是补充一下,堆的实现代码。Heap是抽象类,它有两个子类,MaxHeap和MinHeap。至于它们的function,我不再赘述了,...
  • 堆是一种经过排序的完全二叉树,其中任一非终端节点...而最大-最小堆集结了最大堆最小堆的优点,这也是其名字的由来。 最大-最小堆是最大层和最小层交替出现的二叉树,即最大层结点的儿子属于最小层,最小层结点的儿
  • 2-6 设最小堆(小根堆)的层序遍历结果为 {8, 38, 25, 58, 52, 82, 70, 60}。用线性时间复杂度的算法将该堆调整为最大堆(大根堆),然后连续执行两次删除最大元素操作(DeleteMax)。则该树的中序遍历结果为: ...
  • 深入理解堆(最大堆最小堆及堆排序)

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

    万次阅读 2019-08-15 14:59:56
    顶元素与末尾元素交换,将最大元素"沉"到数组末端;   3).重新调整结构,使其满足定义,然后继续交换顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。 */ for(int j = arr.length-1;...
  • 实际上是一个堆(不指定Comparator时默认为最小堆),通过传入自定义的Comparator函数可以实现大顶堆。 这个特性能让写java的我们少了一大堆的建堆过程啊!!! import java.util.Comparator; import java....
  • 建议读者先去下载《啊哈算法》看大概在P182页的堆,什么是最小堆? ps:如果想进来学习什么是堆的童鞋们,你们不需要再继续往下面阅读啦,对你们有意义的是第一行哦~随后我将此本算法书会长传到csdn上哦~ 而已经...
  • 先是基础:最大堆(大顶堆)和最小堆(小顶堆)详解;然后剖析“堆排序”的实质和思路过程,然后又代码逐步实现!
  • 比如用最大堆求N个数中前K个最小的数,用最小堆求N个数中前K个最大的数。你懂了吗????不懂自己搜吧! 开始正文: 前一阵子一直在写排序的系列文章,最近因为一些事情耽搁了几天,也穿插了几篇其他类别的随笔。今...
  • 堆数的定义 堆树的定义如下: (1)堆树是一颗完全二叉树; (2)堆树中某个节点的值总是不大于或不小于其孩子节点的值; (3)堆树中每个节点的子树都...建立最大堆最小堆的过程,就是对原有的数组中不断交换父亲...
  • 1、完全二叉树:若二叉树的深度为h,则除第h层外,其他层的结点全部达到最大值,且第h层的所有结点都集中在左子树。 2、满二叉树:满二叉树是一种特殊的的完全二叉树,所有层的结点都是最大值。 什么是...
  • 二叉堆(最小堆, 最大堆)介绍与实现

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 212,101
精华内容 84,840
关键字:

最大堆最小堆

友情链接: st.rar