COMPLETE BINARY TREE & PRIORITY QUEUE
二叉树需要维护繁琐的 left/right 内存指针,但 **堆 (Heap)** 是个天才的设计。它是一棵完全二叉树,极其紧凑,因此可以直接被“拍扁”存进一个连续的一维数组里!
无需指针,只需简单的数学运算就能穿梭时空:
节点 [i] 的左孩子是 [2i + 1],右孩子是 [2i + 2],父亲是 [(i - 1) / 2]。
本沙盘演示 **大顶堆 (Max Heap)**:根节点永远是全场最大的 VIP!
插入数组末尾,然后与其父节点 [(i-1)/2] 对比,若更大则**上浮(Swim)**交换。
拔除堆顶[0],将数组末尾元素移至顶端,然后与左右子节点对比,向大的一方**下沉(Sink)**。