精华内容
下载资源
问答
  • 2-6 设最小堆(小根堆)的层序遍历结果为 {8, 38, 25, 58, 52, 82, 70, ...用线性时间复杂度的算法将该堆调整为最大堆(大根堆),然后连续执行两次删除最大元素操作(DeleteMax)。则该树的中序遍历结果为: ...

    2-6 设最小堆(小根堆)的层序遍历结果为 {8, 38, 25, 58, 52, 82, 70, 60}。用线性时间复杂度的算法将该堆调整为最大堆(大根堆),然后连续执行两次删除最大元素操作(DeleteMax)。则该树的中序遍历结果为:

     

    展开全文
  • 比如用最大堆求N个数中前K个最小的数,用最小堆求N个数中前K个最大的数。你懂了吗????不懂自己搜吧! 开始正文: 前一阵子一直在写排序的系列文章,最近因为一些事情耽搁了几天,也穿插了几篇其他类别的随笔。今...
    展开全文
  • 最大堆:根结点的键值是所有堆结点键值中最大者。 最小堆:根结点的键值是所有堆结点键值中最小者。 而最大-最小堆集结了最大堆和最小堆的优点,这也是其名字的由来。 最大-最小堆是最大层和最小层交替出现的二叉树...
    堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。
    最大堆和最小堆是二叉堆的两种形式。
    最大堆:根结点的键值是所有堆结点键值中最大者。
    最小堆:根结点的键值是所有堆结点键值中最小者。
    而最大-最小堆集结了最大堆和最小堆的优点,这也是其名字的由来。
    最大-最小堆是最大层和最小层交替出现的二叉树,即最大层结点的儿子属于最小层,最小层结点的儿子属于最大层。
    以最大(小)层结点为根结点的子树保有最大(小)堆性质:根结点的键值为该子树结点键值中最大(小)项。 
                                                                                                                                                                                                   
    一:堆
      我们构建一个堆类,用最大堆和最小堆来继承他。
    #ifndef _HEAP_H
    #define _HEAP_H
    
    #include <iostream>
    using namespace std;
    
    enum{DEFAULT_SIZE = 10};
    
    template <typename T>
    class Heap{
    public:
    	Heap() = default;
    	virtual ~Heap() = default;
    public: 
    	virtual void show_heap()const = 0;
    	virtual bool insert_heap(const T&) = 0;
    	virtual bool remove_heap(T &) = 0;
    };
    
    //public interface
    
    #endif   /*Heap.h*/
    

    二:最大堆
      下面是最大堆的实现:
    #ifndef _MAXHEAP_H
    #define _MAXHEAP_H
    
    #include <iostream>
    
    #include "Heap.h"
    
    template <typename T>
    class MaxHeap : public Heap<T>{
    public:
    	MaxHeap(int);
    	MaxHeap(const T [], const int);
    	~MaxHeap();
    public:
    	bool insert_heap(const T&);
    	bool remove_heap(T &);
    
    	void show_heap()const;
    protected:
    	void sift_down(int, int);
    	void sift_up(int);
    private:
    	T *heap;
    	int size;
    	int capacity;
    };
    
    //public interface
    
    template <typename T>
    MaxHeap<T>::MaxHeap(int sz = DEFAULT_SIZE)
    {
    	capacity = sz > DEFAULT_SIZE ? sz : DEFAULT_SIZE;
    	heap = new T[capacity];
    	assert(heap != NULL);
    	size = 0;
    }
    
    template <typename T>
    MaxHeap<T>::MaxHeap(const T arr[], const int arrSize)
    {
    	capacity = arrSize > DEFAULT_SIZE ? arrSize : DEFAULT_SIZE;
    	heap = new T[capacity];
    	assert(heap != NULL);
    	size = arrSize;
    
    	for(int i=0; i<size; ++i)
    		heap[i] = arr[i];
    	
    	int curPos = size/2 - 1;
    	while(curPos >= 0){
    		sift_down(curPos, size-1);
    		--curPos;
    	}
    	
    }
    
    template <typename T>
    MaxHeap<T>::~MaxHeap()
    {
    	delete []heap;
    	heap = NULL;
    	capacity = size = 0;
    }
    
    template <typename T>
    bool MaxHeap<T>::insert_heap(const T& val)
    {
    	if(size >= capacity)
    		return false;
    	
    	heap[size] = val;
    	sift_up(size);
    	++size;
    	return true;
    }
    
    template <typename T>
    bool MaxHeap<T>::remove_heap(T &val)
    {
    	if(size <= 0)
    		return false;
    	
    	val = heap[0];
    	heap[0] = heap[size-1];
    	--size;
    	sift_down(0, size-1);
    	return true;
    }
    
    template <typename T>
    void MaxHeap<T>::show_heap()const
    {
    	for(int i=0; i<size; ++i)
    		std::cout << heap[i] << " ";
    	std::cout << std::endl;
    }
    
    //protected interface
    
    template <typename T>
    void MaxHeap<T>::sift_down(int start, int end)
    {
    	int i = start;
    	int j = i*2 + 1;
    
    	T tmp = heap[i];
    	while(j <= end){
    		if(j+1 <= end && heap[j] < heap[j+1])
    			++j;
    		if(tmp < heap[j])
    			heap[i] = heap[j];
    		else
    			break;
    
    		i = j;
    		j = j*2 + 1;
    	}
    	heap[i] = tmp;
    }
    
    template <typename T>
    void MaxHeap<T>::sift_up(int start)
    {
    	int j = start;
    	int i = (start-1) / 2;
    
    	T tmp = heap[j];
    	while(j > 0){
    		if(tmp < heap[i])
    			break;
    		else
    			heap[j] = heap[i];
    		
    		j = i;
    		i = (i-1) / 2;
    	}
    	heap[j] = tmp;
    }
    
    #endif   /*MaxHeap.h*/
    

    三:最小堆
      下面是最小堆的实现:
    #ifndef _MINHEAP_H
    #define _MINHEAP_H
    
    #include <assert.h>
    
    #include "Heap.h"
    
    template <typename T>
    class MinHeap : public Heap<T>{
    public:
    	MinHeap(int);
    	MinHeap(const T [], const int );
    	~MinHeap();
    public:
    	bool insert_heap(const T&);
    	bool remove_heap(T &);
    	
    	void show_heap()const;
    protected:
    	void sift_down(int, int);
    	void sift_up(int);
    private:
    	T* heap;
    	int size;
    	int capacity;
    };
    
    //interface
    
    template <typename T>
    MinHeap<T>::MinHeap(int sz = DEFAULT_SIZE)
    {
    	capacity = sz > DEFAULT_SIZE ? sz : DEFAULT_SIZE;
    	heap = new T[capacity];
    	assert(heap != NULL);
    	size = 0;
    }
    
    template <typename T>
    MinHeap<T>::MinHeap(const T arr[], const int arrSize)
    {
    	capacity = arrSize > DEFAULT_SIZE ? arrSize : DEFAULT_SIZE;
    	heap = new T[capacity];
    	assert(heap != NULL);
    	size = arrSize;
    
    	for(int i=0; i<arrSize; ++i)
    		heap[i] = arr[i];
    	
    	int curPos = arrSize/2 - 1;
    	while(curPos >= 0){
    		sift_down(curPos, arrSize-1);
    		--curPos;
    	}
    }
    
    template <typename T>
    MinHeap<T>::~MinHeap()
    {
    	delete []heap;
    	heap = NULL;
    	capacity = size = 0;
    }
    
    template <typename T>
    bool MinHeap<T>::insert_heap(const T& val)
    {
    	if(size >= capacity)
    		return false;
    	
    	heap[size] = val;
    	sift_up(size);
    	++size;
    	return true;
    }
    
    template <typename T>
    bool MinHeap<T>::remove_heap(T& val)
    {
    	if(size <= 0)
    		return false;
    	
    	val = heap[0];
    	heap[0] = heap[size-1];
    	--size;
    	sift_down(0, size-1);
    	return true;
    }
    
    template <typename T>
    void MinHeap<T>::show_heap()const
    {
    	for(int i=0; i<size; ++i)
    		std::cout << heap[i] << " ";
    	std::cout << std::endl;
    }
    
    //protected interface
    
    template <typename T>
    void MinHeap<T>::sift_down(int start, int end)
    {
    	int i = start;
    	int j = start*2 + 1;
    
    	T tmp = heap[i];
    	while(j <= end){
    		if(j+1 < end && heap[j] > heap[j+1])
    			++j;
    		if(tmp < heap[j])
    			break;
    		else
    			heap[i] = heap[j];
    		
    		i = j;
    		j = j*2 + 1;
    	}
    	heap[i] = tmp;
    }
    
    template <typename T>
    void MinHeap<T>::sift_up(int start)
    {
    	int j = start;
    	int i = (start-1) / 2;
    
    	T tmp = heap[j];
    	while(j > 0){
    		if(tmp > heap[i])
    			break;
    		else
    			heap[j] = heap[i];
    		j = i;
    		i = (i-1) / 2;
    	}
    	heap[j] = tmp;
    }
    
    #endif
    

    四:测试如下:
    #include "MinHeap.h"
    #include "MaxHeap.h"
    #include <iostream>
    using namespace std;
    
    int main()
    {
    	int array[] = {23, 9, 34, 2, 56, 89, 35, 54};
    	
    	cout << "***************************MinHeap***************************" << endl;
    	MinHeap<int> min_heap(array, sizeof(array)/sizeof(int));
    	
    	min_heap.show_heap();
    	min_heap.insert_heap(1);
    	min_heap.show_heap();
    	for(int i=0; i<9; ++i){
    		int val;
    		min_heap.remove_heap(val);
    		cout << val << " ";
    	}
    	cout << endl;
    	
    	MaxHeap<int> max_heap(array, sizeof(array)/sizeof(int));
    	cout << "***************************MaxHeap**************************" << endl; 
    	max_heap.show_heap();
    	max_heap.insert_heap(99);
    	max_heap.show_heap();
    	for(int i=0; i<9; ++i){
    		int val;
    		max_heap.remove_heap(val);
    		cout << val << " ";
    	}
    	cout << endl;
    	
    	return 0;
    }
    
    结果如下:




    展开全文
  • 关于最大堆 什么是最大堆和最小堆?最大(小)堆是指在树中,存在一个结点而且该结点有儿子结点,该结点的data域值都不小于(大于)其儿子结点的data域值,并且它是一个完全二叉树(不是满二叉树)。注意区分选择树...

    原文地址

    我有一个不成熟的建议:老老实实花1个小时把这篇文章仔细看完,关于堆的各种操作一目了然了。

    关于最大堆

    什么是最大堆和最小堆?最大(小)堆是指在树中,存在一个结点而且该结点有儿子结点,该结点的data域值都不小于(大于)其儿子结点的data域值,并且它是一个完全二叉树(不是满二叉树)。注意区分选择树,因为选择树(selection tree)概念和最小堆有些类似,他们都有一个特点是“树中的根结点都表示树中的最小元素结点”。同理最大堆的根结点是树中元素最大的。那么来看具体的看一下它长什么样?(最小堆这里省略)

    在这里插入图片描述
    这里需要注意的是:在多个子树中,并不是说其中一个子树的父结点一定大于另一个子树的儿子结点。最大堆是树结构,而且一定要是完全二叉树。

    最大堆ADT

    那么我们在做最大堆的抽象数据类型(ADT)时就需要考虑三个操作:
    (1)、创建一个最大堆;
    (2)、最大堆的插入操作;
    (3)、最大堆的删除操作;
    最大堆ADT如下:

    struct Max_Heap {
      object: 由多个元素组成的完全二叉树,其每个结点都不小于该结点的子结点关键字值
      functions:
        其中heap∈Max_Heap,n,max_size∈int,Element为堆中的元素类型,item∈ Element
        Max_Heap createHeap(max_size)       := 创建一个总容量不大于max_size的空堆
        void max_heap_insert(heap, item ,n) := 插入一个元素到heap中
        Element max_heap_delete(heap,n)     := if(heap不为空) {return 被删除的元素 }else{return NULL}
    }
    ///其中:=符号组读作“定义为”
    

    最大堆内存表现形式

    我们只是简单的定义了最大堆的ADT,为了能够用代码实现它就必须要考虑最大堆的内存表现形式。从最大堆的定义中,我们知道不管是对最大堆做插入还是删除操作,我们必须要保证插入或者删除完成之后,该二叉树仍然是一个完全二叉树。基于此,我们就必须要去操作某一个结点的父结点。
      第一种方式,我们使用链表的方式来实现,那么我们需要添加一个额外的指针来指向该结点的父结点。此时就包括了左子结点指针、右子结点指针和父结点指针,那么空链的数目有可能是很大的,比如叶子结点的左右子结点指针和根结点的父结点指针,所以不选择这种实现方式(关于用链表实现一般二叉树时处理左右子结点指针的问题在线索二叉树中有提及)。
      第二种方式,使用数组实现,在二叉树进行遍历的方法分为:先序遍历、中序遍历、后序遍历和层序遍历。我们可以通过层序遍历的方式将二叉树结点存储在数组中,由于最大堆是完全二叉树不会存在数组的空间浪费。那么来看看层序遍历是怎么做的?对下图的最大堆进行层序遍历:

    在这里插入图片描述
    在这里插入图片描述
    从这里可以看出最后得到的顺序和上面图中所标的顺序是一样的。
      那么对于数组我们怎么操作父结点和左右子结点呢?对于完全二叉树采用顺序存储表示,那么对于任意一个下标为i(1 ≤ i ≤ n)的结点:
    (1)、父结点为:i / 2(i ≠ 1),若i = 1,则i是根节点。
    (2)、左子结点:2i(2i ≤ n), 若不满足则无左子结点。
    (3)、右子结点:2i + 1(2i + 1 ≤ n),若不满足则无右子结点。

    在这里插入图片描述
    最终我们选择数组作为最大堆的内存表现形式。
    基本定义:

    #define MAX_ELEMENTS 20
    #define HEAP_FULL(n) (MAX_ELEMENTS - 1 == n)
    #define HEAP_EMPTY(n) (!n)
    typedef struct {
        int key;
    }element;
    element heap[MAX_ELEMENTS];
    

    下面来看看最大堆的插入、删除和创建这三个最基本的操作。

    最大堆的插入

    最大堆的插入操作可以简单看成是“结点上浮”。当我们在向最大堆中插入一个结点我们必须满足完全二叉树的标准,那么被插入结点的位置的是固定的。而且要满足父结点关键字值不小于子结点关键字值,那么我们就需要去移动父结点和子结点的相互位置关系。具体的位置变化,可以看看下面我画的一个简单的图。

    void insert_max_heap(element item ,int *n){
        if(HEAP_FULL(*n)){
          return;
        }
        int i = ++(*n);
        for(;(i != 1) && (item.key > heap[i/2].key);i = i / 2){/// i ≠ 1是因为数组的第一个元素并没有保存堆结点
          heap[i] = heap[i/2];/// 这里其实和递归操作类似,就是去找父结点
        }
        heap[i] = item;
    }
    

    在这里插入图片描述
    由于堆是一棵完全二叉树,存在n个元素,那么他的高度为:log2(n+1),这就说明代码中的for循环会执行O(log2(n))次。因此插入函数的时间复杂度为:O(log2(n))。

    最大堆的删除

    最大堆的删除操作,总是从堆的根结点删除元素。同样根元素被删除之后为了能够保证该树还是一个完全二叉树,我们需要来移动完全二叉树的最后一个结点,让其继续符合完全二叉树的定义,从这里可以看作是最大堆最后一个结点的下沉(也就是下文提到的结点1)操作。例如在下面的最大堆中执行删除操作:

    在这里插入图片描述
    现在对上面👆最大堆做删除,对于最大堆的删除,我们不能自己进行选择删除某一个结点,我们只能删除堆的根结点。(⚠️⚠️⚠️)

    • 第一步,我们删除上图中的根结点20;
    • 当删除根结点20之后明显不是一个完全二叉树,更确切地说被分成了两棵树。
    • 我们需要移动子树的某一个结点来充当该树的根节点,那么在(15,2,14,10,1)这些结点中移动哪一个呢?显然是移动结点1,如果移动了其他结点(比如14,10)就不再是一个完全二叉树了。

    对上面三步图示如下:

    在这里插入图片描述
    显然现在看来该二叉树虽然是一个完全二叉树,但是它并不符合最大堆的相关定义,我们的目的是要在删除完成之后,该完全二叉树依然是最大堆。因此就需要我们来做一些相关的操作!

    1)、此时在结点(152)中选择较大的一个和1做比较,即15 > 1的,所以15上浮到之前的20的结点处。
    2)、同第1步类似,找出(1410)之间较大的和1做比较,即14>1的,所以14上浮到原来15所处的结点。
    3)、因为原来14的结点是叶子结点,所以将1放在原来14所处的结点处。
    

    在这里插入图片描述

    element delete_max_heap(int *n){
      int parent, child;
      element temp, item;
      temp = heap[--*n];
      item = heap[1];
      parent = 1,child=2;
      for(;child <= *n; child = child * 2){
       if( (child < *n) && heap[child].key < heap[child+1].key){/// 这一步是为了看当前结点是左子结点大还是右子结点大,然后选择较大的那个子结点
            child++;
          }
          if(temp.key >= heap[child].key){
            break;
          }
          heap[parent] = heap[child];///这就是上图中第二步和第三步中黄色部分操作
          parent = child;/// 这其实就是一个递归操作,让parent指向当前子树的根结点
       }
      heap[parent] = temp;
      return item;
    }
    

    同最大堆的插入操作类似,同样包含n个元素的最大堆,其高度为:log2(n+1),其时间复杂度为:O(log2(n))。

    总结:由此可以看出,在已经确定的最大堆中做删除操作,被删除的元素是固定的,需要被移动的结点也是固定的,这里我说的被移动的元素是指最初的移动,即最大堆的最后一个元素。移动方式为从最大的结点开始比较。

    最大堆的创建

    为什么要把最大堆的创建放在最后来讲?因为在堆的创建过程中,有两个方法。会分别用到最大堆的插入和最大堆的删除原理。创建最大堆有两种方法:
    (1)、先创建一个空堆,然后根据元素一个一个去插入结点。由于插入操作的时间复杂度为O(log2(n)),那么n个元素插入进去,总的时间复杂度为O(n * log2(n))。
    (2)、将这n个元素先顺序放入一个二叉树中形成一个完全二叉树,然后来调整各个结点的位置来满足最大堆的特性。
    现在我们就来试一试第二种方法来创建一个最大堆:假如我们有12个元素分别为:

    {79,66,43,83,30,87,38,55,91,72,49,9}
    

    将上诉15个数字放入一个二叉树中,确切地说是放入一个完全二叉树中,如下:
    在这里插入图片描述
    但是这明显不符合最大堆的定义,所以我们需要让该完全二叉树转换成最大堆!怎么转换成一个最大堆呢?
      最大堆有一个特点就是其各个子树都是一个最大堆,那么我们就可以从把最小子树转换成一个最大堆,然后依次转换它的父节点对应的子树,直到最后的根节点所在的整个完全二叉树变成最大堆。那么从哪一个子树开始调整?
    我们从该完全二叉树中的最后一个非叶子节点为根节点的子树进行调整,然后依次去找倒数第二个倒数第三个非叶子节点…

    具体步骤

    在做最大堆的创建具体步骤中,我们会用到最大堆删除操作中结点位置互换的原理,即关键字值较小的结点会做下沉操作。

    • 1)、就如同上面所说找到二叉树中倒数第一个非叶子结点87,然后看以该非叶子结点为根结点的子树。查看该子树是否满足最大堆要求,很明显目前该子树满足最大堆,所以我们不需要移动结点。该子树最大移动次数为1。

    在这里插入图片描述

    • 2)、现在来到结点30,明显该子树不满足最大堆。在该结点的子结点较大的为72,所以结点72和结点30进行位置互换。该子树最大移动次数为1。
    • 在这里插入图片描述
    • 3)、同样对结点83做类似的操作。该子树最大移动次数为1。
      在这里插入图片描述
    • 4)、现在来到结点43,该结点的子结点有{87,38,9},对该子树做同样操作。由于结点43可能是其子树结点中最小的,所以该子树最大移动次数为2。

    在这里插入图片描述

    • 5)、结点66同样操作,该子树最大移动次数为2。
      在这里插入图片描述
    • 6)、最后来到根结点79,该二叉树最高深度为4,所以该子树最大移动次数为3。
      在这里插入图片描述
      自此通过上诉步骤创建的最大堆为:
      在这里插入图片描述
      所以从上面可以看出,该二叉树总的需要移动结点次数最大为:10。

    代码实现

      void create_max_heap(void){
            int total = (*heap).key;
            /// 求倒数第一个非叶子结点
            int child = 2,parent = 1;
            for (int node = total/2; node>0; node--) {
                parent = node;
                child = 2*node;
                int max_node = 2*node+1;
                element temp = *(heap+parent);
                for (; child <= total; child *= 2,max_node = 2*parent+1) {
                    if (child+1 <= total && (*(heap+child)).key < (*(heap+child+1)).key) {
                        child++;
                    }
                    if (temp.key > (*(heap+child)).key) {
                        break;
                    }
                    *(heap+parent) = *(heap+child);
                    parent = child;
                }
                *(heap+parent) = temp;
            }
        }
    
    /**
     *
     * @param heap  最大堆;
     * @param items 输入的数据源
     * @return 1成功,0失败
     */
    int create_binary_tree(element *heap,int items[MAX_ELEMENTS]){
        int total;
        if (!items) {
            return 0;
        }
        element *temp = heap;
        heap++;
        for (total = 1; *items;total++,(heap)++,items = items + 1) {
            element ele = {*items};
            element temp_key = {total};
            *temp = temp_key;
            *heap = ele;
        }
        return 1;
    }
    ///函数调用
    int items[MAX_ELEMENTS] = {79,66,43,83,30,87,38,55,91,72,49,9};
    element *position = heap;
    create_binary_tree(position, items);
    for (int i = 0; (*(heap+i)).key > 0; i++) {
      printf("binary tree element is %d\n",(*(heap + i)).key);
    }
    create_max_heap();
    for (int i = 0; (*(heap+i)).key > 0; i++) {
      printf("heap element is %d\n",(*(heap + i)).key);
    }
    

    上诉代码在我机器上能够成功的构建一个最大堆。由于该完全二叉树存在n个元素,那么他的高度为:log2(n+1),这就说明代码中的for循环会执行O(log2(n))次。因此其我理解的平均运行时间为:O(log2(n))。而其上界为当该二叉树为满二叉树时其时间复杂度为O((n)。

    堆排序

    堆排序要比空间复杂度为O(n)的归并排序要慢一些,但是要比空间复杂度为O(1)的归并排序要快!
      通过上面最大堆创建一节中我们能够创建一个最大堆。出于该最大堆太大,我将其进行缩小以便进行画图演示。

    在这里插入图片描述
    最大堆的排序过程其实是和最大堆的删除操作类似,由于最大堆的删除只能在根结点进行,当将根结点删除完成之后,就是将剩下的结点进行整理让其符合最大堆的标准。

    • 1)、把最大堆根结点91“删除”,第一次排序图示:

    在这里插入图片描述
    进过这一次排序之后,91就处在最终的正确位置上,所以我们只需要对余下的最大堆进行操作!这里需要注意一点:
    ⚠️⚠️⚠️注意,关于对余下进行最大堆操作时:
    并不需要像创建最大堆时,从倒数第一个非叶子结点开始。因为在我们只是对第一个和最后一个结点进行了交换,所以只有根结点的顺序不满足最大堆的约束,我们只需要对第一个元素进行处理即可

    • 2)、继续对结点87进行相同的操作:

    在这里插入图片描述
    同样,87的位置确定。

    • 3)、现在我们来确定结点83的位置:

    在这里插入图片描述

    • 4)、经过上诉步骤就不难理解堆排序的原理所在,最后排序结果如下:

    在这里插入图片描述
    经过上诉多个步骤之后,最终的排序结果如下:

    [38437279838791]
    

    很明显这是一个正确的从小到大的顺序。

    编码实现

    这里需要对上面的代码进行一些修改!因为在排序中,我们的第0个元素是不用去放一个哨兵的,我们的元素从原来的第一个位置改为从第0个位置开始放置元素。

    void __swap(element *lhs,element *rhs){
        element temp = *lhs;
        *lhs = *rhs;
        *rhs = temp;
    }
    
    int create_binarytree(element *heap, int items[MAX_SIZE], int n){
        if (n <= 0) return 0;
        for (int i = 0; i < n; i++,heap++) {
            element value = {items[i]};
            *heap = value;
        }
        return 1;
    }
    
    void adapt_maxheap(element *heap ,int node ,int n){
        int parent = node - 1 < 0 ? 0 : node - 1;
        int child = 2 * parent + 1;/// 因为没有哨兵,所以在数组中的关系由原来的:parent = 2 * child => parent = 2 * child + 1
        int max_node = max_node = 2*parent+2 < n - 1 ? 2*parent+2 : n - 1;
        element temp = *(heap + parent);
        for (;child <= max_node; parent = child,child = child * 2 + 1,max_node = 2*parent+2 < n - 1 ? 2*parent+2 : n - 1) {
            if ((heap + child)->key <= (heap + child + 1)->key && child + 1 < n) {
                child++;
            }
            if ((heap + child)->key < temp.key) {
                break;
            }
            *(heap + parent) = *(heap + child);
        }
        *(heap + parent) = temp;
    }
    
    int create_maxheap(element *heap ,int n){
    
        for (int node = n/2; node > 0; node--) {
            adapt_maxheap(heap, node, n);
        }
        return 1;
    }
    
    void heap_sort(element *heap ,int n){
        ///创建一个最大堆
        create_maxheap(heap, n);
        ///进行排序过程
        int i = n - 1;
        while (i >= 0) {
            __swap(heap+0, heap + i);/// 将第一个和最后一个进行交换
            adapt_maxheap(heap, 0, i--);///将总的元素个数减一,适配成最大堆,这里只需要对首元素进行最大堆的操作
        }
    }
    

    调用:

    /// 堆排序
    int n = 7;
    int items[7] = {87,79,38,83,72,43,91};
    element heap[7];
    create_binarytree(heap, items, n);
    heap_sort(heap, n);///38,43,72,79,83,87,91
    

    在实现堆排序时最需要注意的就是当没有哨兵之后,父结点和左右孩子结点之间的关系发生了变化:

    parent = 2 * child + 1;///左孩子
    parent = 2 * child + 2;///右孩子
    

    关于对排序相关的知识点已经整理完了。其时间复杂度和归并排序的时间时间复杂度是一样的O(N*LogN)。

    结束语

    当我们在做和完全二叉树有关的操作时,对于完全二叉树采用顺序存储表示,需要记住对于任意一个下标为i(1 ≤ i ≤ n)的结点:父结点为:i / 2(i ≠ 1),若i = 1,则i是根节点。左子结点:2i(2i ≤ n), 若不满足则无左子结点。右子结点:2i + 1(2i + 1 ≤ n),若不满足则无右子结点。
      关于最大堆的相关操作(插入、删除、创建和排序)已经一一学习完毕。这些操作中,删除、创建和排序思想非常类似,都是操作结点下沉。而插入操作相反,类似上浮的操作!

    展开全文
  • 堆的插入与删除最大堆

    千次阅读 2018-08-05 15:05:57
     这里以最大堆为例子,先将要插入的元素放在堆的末尾,然后将其与父节点比较,如果比父节点大,那么就与父节点交换。 重复此操作,这里有个技巧,可以在堆的上面设一个很大的元素,称为哨兵,这样即使是到了堆顶也...
  • 最大堆(创建、删除、插入和堆排序)
  • 最大堆的插入和删除

    2020-03-23 00:38:43
    首先,我们要了解堆这种数据结构,这里的堆具有完全二叉树的结构,并且堆树中某个节点的值总是不大于或不小于其孩子节点的值(‘不大于’的情况叫最小堆,‘不小于的情况叫最大堆’),堆树中每个节点的子树都是堆树...
  • 1、完全二叉树:若二叉树的深度为h,则除第h层外,其他层的结点全部达到最大值,且第h层的所有结点都集中在左子树。 2、满二叉树:满二叉树是一种特殊的的完全二叉树,所有层的结点都是最大值。 什么是...
  • 堆数的定义 堆树的定义如下: (1)堆树是一颗完全二叉树; (2)堆树中某个节点的值总是不大于或不小于其孩子节点的值; (3)堆树中每个节点的子树都...建立最大堆和最小堆的过程,就是对原有的数组中不断交换父亲...
  • 最大堆、最小堆详解

    千次阅读 2018-10-16 15:05:42
    最大堆、最小堆详解 Overview 最大堆和最小堆是二叉堆的两种形式。...文章目录最大堆、最小堆详解Overview一、二叉堆二、最大堆、最小堆详解(以最大堆为例)由上至下的下沉建堆操作(以最大堆为例)...
  • 最大是一棵完全二叉树,也是一棵最大树(即对于每个结点,其关键字的值不小于儿子结点的关键字值)。
  • 堆树(最大堆、最小堆)详解

    万次阅读 多人点赞 2016-03-16 13:30:58
    一、堆树的定义 堆树的定义如下: (1)堆树是一颗完全二叉树; (2)堆树中某个节点的值总是不大于或不小于其孩子节点的值; (3)堆树中每个节点的子树都是堆树。 当父节点的键值总是大于或...以最大堆为例进行讲解
  • 数据结构 堆树(最大堆、最小堆)

    千次阅读 2019-01-09 15:36:10
    当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆,也称大根堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆,也称小根堆。 如下图所示,上边为最大堆,下边为最小堆。 二、堆树的...
  • python实现最大堆,最小堆和堆排序

    千次阅读 2019-04-13 22:35:00
    2. 各个父节点必须大于或小于左右结点, 其中最顶层的根结点必须是最大或者最小的 可以使用list实现,就是按照层序遍历顺序将每个节点上的值存放在数组中。父节点和子节点之间存在如下的关系: i 从...
  • 【数据结构】最大堆的插入与删除

    千次阅读 2017-05-23 21:45:00
    堆最常使用二叉树结构表示,可以看作是一种特殊的完全二叉树,对于一个最大堆来说可以描述为一颗所有非叶节点的子节点的值都小于该节点的完全二叉树,易得根节点的值最大,所以最大堆也叫大根堆。最小堆的描述与最大...
  • 最小堆。最大堆

    万次阅读 2012-11-08 23:00:06
    最大堆和最小堆是二叉堆的两种形式。 最大堆:根结点的键值是所有堆结点键值中最大者,且每个结点的值都比其孩子的值...生成最大堆最大堆通常都是一棵完全二叉树,因此我们使用数组的形式来存储最大堆的值,从1号单
  • 什么是? 优先队列:特殊的队列,取出元素的顺序是依照元素的优先权(关键字)大小,而不是进入队列的先后顺序。...由的定义可以看出,顶元素(即第一个元素)必为最大项(大顶堆)。完全二叉树可以很...
  • 链接1:https://blog.csdn.net/Genios/article/details/8157031 链接2:https://blog.csdn.net/hrn1216/article/details/51465270
  • 建立最大堆

    2017-05-24 15:39:59
    建立最大堆删除最大堆根节点算法类似,都需要依次下滤父结点。 typedef struct HNode *Heap; struct HNode { int *Data;//存储元素的数组; int size; int capacity; }; typedef Heap MaxHeap; typedef Heap ...
  • 最大最小的插入与删除

    千次阅读 2015-07-20 11:05:05
    最大堆、最小堆是一种用可用数组存储,并模拟实现二叉树的数据结构。 最大(小)堆具有以下的显著性质: ●最大(小)堆是一棵树,且是完全二叉树。 ●最大(小)堆是每个根节点都一定大(小)于等于其子节点。 ...
  • Java实现堆(最大堆

    2020-10-16 17:34:26
    1、什么是 现在有这么一个需求,设计一个结构,满足两个操作要求: 删除时,返回该结构的最大值或者最小值的元素 往结构中新增元素 问题:如何组织优先这种结构? 一般数组、链表? 有序数组或者链表? 二叉...
  • 最大堆:就是不不断变得进行树元素替换,最终是树呈现上面数值最大; 最小堆:就是不不断变得进行树元素替换,最终是树呈现上面数值最小;   堆的定义 堆是一种经过排序的完全二叉树或满二叉树,n个元素的序列{...
  • C++实现最大堆和最小堆

    千次阅读 2018-08-19 20:47:17
    最大堆: 任一结点的关键码均大于等于它的左右孩子的关键码,其中堆顶的元素最大。(任一路径中的元素升序排列) 最小堆: 任一结点的关键码均小于等于它的左右孩子的关键码,其中堆顶的元素最小。(任一路径...
  • 最大堆、最小堆C++实现

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

    2017-06-11 22:23:51
    现在我们要利用堆进行排序操作,所以需要的是一种特殊的完全二叉树最大堆。 (当然用最小堆也可以做到,方法是每次取出h[1]的数,然后将h[n]赋值给h[1],同时 n--,不断的进行这个操作直到堆空) 用最大堆的做法就是 1...
  • 详细图文——最大堆

    千次阅读 2019-03-20 20:40:33
    二叉堆是一种特殊的堆,二叉堆是完全二叉树。本文讲解了最大堆的实现过程,尤其是堆的调整操作——siftUp和siftDown。阅读完本文您可以自己实现最大堆了。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 172,729
精华内容 69,091
关键字:

最大堆删除