树-堆 | 智能后端和架构

树-堆

更新时间浏览

TIP

本文主要是介绍树-堆。

定义：
堆的操作
参考文章

深入理解堆（最大堆，最小堆及堆排序）

1、完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。

2、满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。

# 定义：

1、堆是一颗完全二叉树；

2、堆中的某个结点的值总是大于等于（最大堆）或小于等于（最小堆）其孩子结点的值。

3、堆中每个结点的子树都是堆树。

# 堆的操作

假设原始数据为a[]={4,1,3,2,16,9.10.14.8.7},采用顺序存储对应的完全二叉树为：

# 堆的数据结构如下

struct MaxHeap
{
    EType *heap; //存放数据的空间，下标从1开始存储数据，下标为0的作为工作空间，存储临时数据。
    int MaxSize; //MaxSize是存放数据元素空间的大小
    int HeapSize; //HeapSize是数据元素的个数
};
MaxHeap H;

# 1、构造最大堆

基本思想：首先将每个叶子结点视为一个堆，再将每个叶子结点于其父节点一起构成一个包含更多结点的堆。所以在构造堆的时候，首先需要找到最后一个结点的父节点，从这个节点开始构造最大堆，直到该节点前面的所有分支节点都处理完毕。

注意：在二叉树中，若当前节点的下标为 i，则其父节点的下标为 i/2，其左子节点的下标为 i2，其右子节点的下标为i2+1；

# 2、初始化堆

void MaxHeapInit(MaxHeap &H)
{
    for(int i=H.HeapSize/2;i>=1;i--)
    {
        H.heap[0]=H.heap[i];
        int son=i*2;
        while(son<H.HeapSize)
        {
            if(son<H.HeapSize&&H.heap[son]<H.heap[son+1])
                son++;
            if(H.heap[i]>H.heap[son])
                break;
            else if(son<H.heapSize&&H.heap[son]>H.heap[son+1]
                {
                    H.heap[son/2]=H.heap[son];
                    son*=2;
                }
        }
        H.heap[son/2]=H.heap[0];
    }
}

下图是原始数据堆初始化的过程。

# 3、最大堆中插入节点

最大堆中插入节点，先在堆末尾插入该节点，然后按照堆的初始化过程将该节点放入到合适的位置。

void MaxHeapInsert(MaxHeap &H, EType &x)
{
    if(H.HeapSize==H.MaxSize) return false;
    

    int i=++H.HeapSize;
    while(i!=1&&x>H.heap[i/2])
    {
        H.heap[i]=H.heap[i/2];
        i/=2;
    }
    H.heap[i]=x;
    return true;

}

# 4、最大堆中删除节点

将最大堆的最后一个节点放到根节点，然后删除最大值，然后再把新的根节点放到合适的位置

void MaxHeapDelete(MaxHeap &H, EType &x)
{
    if(H.HeapSize==0) return false;
    x=H.heap[1];
    H.heap[0]=H.heap[H.HeapSize--];
    int i=1, son=i*2;
     while(son<H.HeapSize)
        {
            if(son<H.HeapSize&&H.heap[son]<H.heap[son+1])
                son++;
            if(H.heap[i]>H.heap[son])
                break;
             H.heao[i]=H.heap[son];
            i=son;
            son*=2;
        }
        H.heap[i]=H.heap[0];
    return true;
    
}

# 5、堆排序

#include<iostream>
using namespace std;

void swap(int &a, int &b)
{
    int temp=a;
    a=b;
    b=temp;
}

void quick_build(int a[], int len, int root)
{
    int left=root*2+1;
    int flag=left;
    while(left<len)
    {
        int right=left+1;
        while(right<len&&a[right]>a[left])
            flag=right;
        

    }
    if(a[root]<a[flag])
    {
        swap(a[root],a[flag]);
        heap_build(a,len,flag);

}

void quick_sort(int a[], int len)
{
    for(int i=len/2;i>0;i--)
        heap_build(a,len, i);
    for(int j=len-1;j>0;j--)
    {
        swap(a[0],a[j]);
        heap_build(a,0,j);
    }  
        
}

# 参考文章

https://blog.csdn.net/summerlq/article/details/82747940

← 树-哈夫曼树树-完全二叉树和满二叉树 →