为什么二叉堆属于树结构？数组实现的二叉堆是否仍为树？

首先要明确一个最容易被混淆的判断标准：数据结构的分类依据是它的逻辑结构，而非底层的存储实现方式。

先区分两个核心概念 #

• 逻辑结构：定义的是数据元素之间的关联规则，是一个数据结构的本质属性。树结构的核心判定规则非常明确：存在唯一根节点，其余每个节点有且仅有一个父节点，节点间不存在环，整体是层次化的一对多关联关系。只要符合这个规则，不管用什么方式存储，它逻辑上就是树。
• 存储结构：指的是数据实际在内存中的排布方式，只是实现层面的选择。常见的存储方式包括顺序存储（数组）、链式存储（带指针的节点）、索引存储、散列存储，存储方式不会反过来改变上层逻辑结构的分类。

二叉堆的逻辑完全符合树的定义 #

二叉堆本质上就是一棵满足堆序性质的完全二叉树：

• 结构上完全满足完全二叉树的要求：除了最底层外其余所有层的节点数都达到最大值，最底层的节点全部靠左排列，不存在环，有唯一根节点，每个非根节点有唯一父节点，完全符合树的判定标准。
• 它的核心特性——堆序（大顶堆父节点值≥子节点值，小顶堆父节点值≤子节点值），完全是建立在这棵二叉树的父子层级关系上的，不是数组本身自带的属性。

为什么能用数组存二叉堆？ #

恰恰是因为它是完全二叉树，节点的相对位置有严格的规律，根本不需要像普通链式二叉树那样存左右孩子的指针，直接通过数组下标就能算出任意节点的关联节点位置（以0下标为起点为例）：

• 下标为i的节点，左孩子下标为2*i + 1
• 下标为i的节点，右孩子下标为2*i + 2
• 下标为i的非根节点，父节点下标为(i-1) // 2

这种数组存储本质上是把完全二叉树的层次遍历结果按顺序放进连续内存里，只是比链式存储省了指针开销、访问效率更高，并没有消解掉节点之间的父子层级关联。
举个很简单的类比：你也可以用数组存图的邻接矩阵，总不能说图这种多对多的非线性结构，因为用数组存了就变成线性结构了吧？

直接回应核心疑问 #

用数组实现的二叉堆，逻辑上依然是完全二叉树，属于树结构。“用线性结构的数组存储”只是实现手段，不会改变它本身的逻辑结构属性。

内容的提问来源于stack exchange，提问作者kay