斜堆

一、什么是斜堆？

斜堆（Skew Heap），也称斜树（Skew Tree），自适应堆(Self-Adjusting Heap)，是一种自平衡二叉堆数据结构。

斜堆是左倾堆（Leftist Heap）的一个变种，只是斜堆的节点中没有 NPL 这个属性而已。

斜堆的主要特点包括：

左倾堆

一、什么是左倾堆？

左倾堆（Leftist Heap），也称为左偏树（Leftist Tree）、左偏堆，最左堆等。

和二叉堆（即常见的堆，基于数组实现的完全堆）一样，左倾堆也是优先队列的一种实现方式。

只不过左倾堆具有一些特殊的性质：

索引堆

一、什么是索引堆？

索引堆（Index Heap）是二叉堆的一个变种，是二叉堆的一种增强。

相比于二叉堆只能访问堆顶元素，索引堆可以通过索引访问堆中的任意元素。

比如下面的索引堆：

1
2
3
4
5

      1(30)      
   /        \   
4(28)       3(16)  
   \         /    
  5(22)    2(12)    

除了可以直接访问堆顶元素 30，还可以通过索引访问其他元素：

堆

一、是什么？

在逻辑意义上，堆是一棵二叉树，类似这样：

1
2
3
4
5
6
7

  大值堆                    小值堆

    30                        14    
 /      \                  /      \ 
28      16                22      16
  \    /                 /       /  
  22  12                24      26  

堆的特性：

• 是一棵二叉树
• 节点是局部有序的（不像 BST 那样整体有序）

局部有序的意思是：