单调栈

一、什么是单调栈？

单调栈（Monotonic Stack）是一种特殊的栈，在栈的「先进后出」基础上，要求「从栈顶到栈底的元素是单调的（递增或递减）」。

与普通栈不同，单调栈的元素是按照特定的单调性（递增或递减）排列的：

1
2
3
4
5
6
7

 普通栈        单调栈

|     |       |     |                    
|     |       |     |                     
|  3  |       |  1  |    <-- 栈顶
|  1  |       |  2  |                 
|__2__|       |__3__|    <-- 栈底

按照单调栈的元素是按照特定的单调性，可分为两种类型：

二叉搜索树

一、结构定义

二叉搜索树（binary search tree），也称为二叉查找树，是一种二叉树，同时还满足了以下的条件：

1. 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
2. 任意节点的左、右子树也是二叉搜索树

相比于普通二叉树，二叉搜索树的节点之间带有大小关系，这使得二叉搜索树可以支持快速的查找、插入、删除操作。

二叉树

一、什么是二叉树？

1.1 二叉树的定义

• 由一系列节点组成的有限集合，每个节点都有且仅有 2 个子节点（空节点也算在内）
• 每个子节点构成一棵子树，并且子树之间没有交集

1.2 二叉树的结构

队列

一、结构特性

基本定义：

• 队列是一种遵循先入先出规则的线性数据结构

主要特点：

• 数据是先进先出，后进后出
• 只允许从队首入队，从队尾出队

队列的两端分别称为「队首」和「队尾」。

栈

一、结构特性

基本定义：

• 栈是一种遵循先入后出的逻辑的线性数据结构

主要特点：

• 数据是先入后出，后入先出
• 只允许在栈的一端操作数据

栈的两端分别称为“栈顶”和“栈底”：

链表

一、结构特性

链表是通过指针将一系列离散的内存块串联在一起的线性表数据结构。

主要特点：

• 线性表数据结构
• 离散的内存空间
• 指针关联
• 动态申请内存空间

数组

一、结构特性

基本定义：

• 数组是存放在连续内存空间上的相同类型数据的线性表结构

主要特点：

• 线性表数据结构
• 连续的内存空间
• 相同类型的数据

斜堆

一、什么是斜堆？

斜堆（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，还可以通过索引访问其他元素：