重要的概念
要讲到堆,先要说两个关于二叉树的概念
满二叉树:一个二叉树如果每一层的节点数都是最大值,那么这个二叉树就是满二叉树
完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是满二叉树的变形,对于深度为k的树有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点
上面所展示的就是满二叉树和完全二叉树
树的存储方式
顺序存储
任何一个数据结构在内存中都要以一定的方式存储起来,那么具体如何存储起来?有下面的规则
首先是顺序存储,也就是用顺序表的形式存储,存储形式如下:
但很明显,这样的存储对于非完全二叉树来说会造成十分严重的内存浪费
链式存储
链式存储相比起顺序存储各有优势,链式存储的规则如下:
定义一个结构体,结构体中包含这三个成员,这三个成员就可以包含一个树的所有信息
==下面重点介绍的是二叉树的顺序结构是如何实现的==
堆的概念
首先要明确,这里的堆和malloc的堆并不是一个意思,前者的意思是一种数据结构,而后者是操作系统的一部分区域
堆是一种完全二叉树,它满足下面的性质
堆中某个节点的值总是不大于或不小于其父节点的值
堆总是一棵完全二叉树
那为什么是不大于或不小于?因为堆也是有划分的,堆分为大堆和小堆
在介绍大堆和小堆之前,先说明堆的顺序存储是如何存储的,以下面这个图为例
上图是一个完全二叉树,其中二叉树的父亲节点总是小于孩子节点,那么这就是小堆,而在内存中的存储形式如下图所示,存储的时候确实是按照数组存储,顺序遵循由上到下由左到右的顺序进行存储
大堆和上图基本一致,之时父亲节点总是大于孩子节点