Tree

tree.png

概念与性质

• 树可以没有结点，这种情况下把树称为空树（empty tree）
• 树的层次（layer）从根结点开始算起，即根结点为第一层
• 把结点的子树棵数称为结点的度（degree）,而树中结点的最大的度称为树的度（也称树的宽度），例如图9-1中三棵树的度分别为2、3、5
• 由于一条边连接两个顶点，且树中不存在环，因此对有n个结点的树，边数一定是n-1
• 叶子结点被定义为度为0的结点，因此当树中只有一个结点（即只有根结点）时，根结点也算作叶子结点
• 结点的深度（depth）是指从根结点（深度为1）开始自顶向下逐层累加至该结点时的深度；结点的高度（height）是指从最底层叶子结点（高度为1）开始自底向上逐层累加至该结点时的高度值。树的深度是指树中结点的最大深度，树的高度是指树中结点的最大高度。对树而言，深度和高度是相等的，例如图9-1中的三棵树的深度和高度分别是4、4、2，但具体到某个结点来说深度和高度就不一定相等了。

二叉树

binaryTree.png

递归定义

1. 要么二叉树没有根结点，是一课空树
2. 要么二叉树由根结点、左子树、右子树组成，且左子树和右子树都是二叉树

满二叉树：每一层的结点个数都达到了当层能达到的最大结点树。图9-2中的树E即为一棵满二叉树
完全二叉树：除了最下面一层之外，其余层的结点个数都达到了该层能达到的最大结点数，且最下面一层只能从左至右连续存在若干结点。图9-2中的树DE均为一棵完全二叉树。

存储结构与基本操作

存储一般用链表

struct node {
    typename data;   // 数据域
    node* lchild;   // 指向左子树根结点的指针
    node* rchild;   // 指向右子树根结点的指针
};

结点新建

node* newNode(int v) {
    node* Node = new Node;   // 申请一个node型变量的地址空间
    Node->data = v;
    Node->lchild = Node->rchild = NULL;   // 初始状态下没有左右孩子
    return Node;   // 返回新建结点的地址
}

查找、修改

void search(node* root, int x, int newdata) {
    if(root == NULL) {   // 递归边界
        return;   
    }
    if(root->data == x) {
        root->data = newdata;
        return;
    }
    search(root->lchild, x, newdata);
    search(root->rchild, x, newdata);
}

插入

二叉树结点的插入位置就是查找失败的位置，因此在递归查找过程中一定是只根据二叉树的性质来选择左子树或右子树中的一棵子树进行递归。

void insert(node* &root, int x) {   
    if(root == NULL) {
        root = newNode(x);
        return;
    }
    if(选择左右) {
        insert(root->lchild, x);
    } else {
        insert(root->rchild, x);
    }
}

注意根结点指针root使用引用&，这样在函数中修改root会直接修改原变量。如果函数中需要新建结点，即对二叉树的结构做出修改，就需要加引用；如果只是修改当前已有结点的内容（root->data），或仅仅是遍历树，就不用加引用。

二叉树的建立

node* Create(int data[], int n) {
    node* root = NULL;   // 新建根结点root
    for(int i=0; i<n; i++) {
        insert(root, data[i]);
    }
    return root;
}

完全二叉树的存储

对于完全二叉树，除了用链表存储，还可以用数组（大小为2^k，k为完全二叉树最大高度）存储。把它的所有结点按从上到下，从左到右的顺序进行编号（从1开始），那么对于任何一个结点（设编号为x），其左孩子的编号一定是2x，而右孩子的编号一定是2x+1。

该数组中元素存放的顺序恰好为该完全二叉树的层次遍历序列。

判断某个结点是否为叶子结点的标志为：该结点的左孩子编号大于结点总数

判断某个结点是否为空结点的标志为：该结点的编号大于结点总数

二叉树的遍历

• 先序遍历：根结点->左子树->右子树（DFS）
• 中序遍历：左子树->根结点->右子树（DFS）
• 后序遍历：左子树->右子树->根结点（DFS）
• 层次遍历：从上到下，从左至右（BFS）

先序遍历

void preOrder(node* root) {
    if(root == NULL) {
        return;
    }
    printf("%d\n", root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

对一棵二叉树的先序遍历，序列的第一个一定是根结点

中序遍历

void inOrder(node* root) {
    if(root == NULL) {
        return;
    }
    inOrder(root->lchild);
    printf("%d\n", root->data);
    inOrder(root->rchild);
}

只要知道根结点，就可以通过根结点在中序遍历序列中的位置区分出左子树和右子树

后序遍历

void postOrder(node* root) {
    if(root == NULL) {
        return;
    }
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("%d\n", root->data);
}

对后序遍历序列来说，序列的最后一个一定是根结点

无论是先序遍历还是后序遍历，都必须还要知道中序遍历才能唯一地确定一棵树

层次遍历

void layerOrder(node* root) {
    queue<node*> q;
    q.push(root);
    while(!q.empty()) {
        node* top = q.front();
        q.pop();
        printf("%d", top->data);
        if(top->lchild != NULL) {
            q.push(top->lchild);
        }
        if(top->rchild != NULL) {
            q.push(top->rchild);
        }
    }
}

已知前序或后序遍历序列，再加上中序遍历序列，恢复原二叉树

#include<cstdio>
#include<queue>
using namespace std;

struct node {
    char data;
    node* lchild;
    node* rchild;
};

char preOrder[]={'A', 'B', 'D', 'E', 'C', 'F'};
char inOrder[]={'D', 'B', 'E', 'A', 'C', 'F'};
char postOrder[]={'D', 'E', 'B', 'F', 'C', 'A'};

// 已知前序和中序，恢复
node* restoreFromPre(int preL, int preR, int inL, int inR) {
    if(preL>preR) {
        return NULL;
    }
    node* root=new node;
    root->data=preOrder[preL];
    int k;
    for(k=inL; k<=inR; k++) {
        if(inOrder[k]==preOrder[preL]) {
            break;
        }
    }
    int numLeft=k-inL; //左子树节点数
    root->lchild=restoreFromPre(preL+1, preL+numLeft, inL, k-1);
    root->rchild=restoreFromPre(preL+numLeft+1, preR, k+1, inR);
    return root;
}

// 已知后序和中序，恢复
node* restoreFromPost(int postL, int postR, int inL, int inR) {
    if(postL>postR) {
        return NULL;
    }
    node* root=new node;
    root->data=postOrder[postR];
    int k;
    for(k=inL; k<=inR; k++) {
        if(inOrder[k]==postOrder[postR]) {
            break;
        }
    }
    int numLeft=k-inL; //左子树节点数
    root->lchild=restoreFromPost(postL, postL+numLeft-1, inL, k-1);
    root->rchild=restoreFromPost(postL+numLeft, postR-1, k+1, inR);
    return root;
}

// 前序遍历
void prePrint(node *root) {
    if(root == NULL) {
        return;
    }
    printf("%c ", root->data);
    if(root->lchild != NULL) {
        prePrint(root->lchild);
    }
    if(root->rchild != NULL) {
        prePrint(root->rchild);
    } 
}

// 中序遍历
void inPrint(node *root) {
    if(root == NULL) {
        return;
    }
    if(root->lchild != NULL) {
        inPrint(root->lchild);
    }
    printf("%c ", root->data);
    if(root->rchild != NULL) {
        inPrint(root->rchild);
    } 
}

// 后序遍历
void postPrint(node *root) {
    if(root == NULL) {
        return;
    }
    if(root->lchild != NULL) {
        postPrint(root->lchild);
    }
    if(root->rchild != NULL) {
        postPrint(root->rchild);
    }
    printf("%c ", root->data);
}

// 层次遍历
void layerPrint(node *root) {
    queue<node*> q;
    q.push(root);
    while(!q.empty()) {
        node* top = q.front();
        q.pop();
        printf("%c ", top->data);
        if(top->lchild != NULL) {
            q.push(top->lchild);
        }
        if(top->rchild != NULL) {
            q.push(top->rchild);
        }
    }
}

int main() {
    node* root = restoreFromPost(0, 5, 0, 5);
    inPrint(root);
    printf(" \n");
    //layerPrint(root);
    return 0;
}

二叉查找树(BinarySearchTree-BST)

定义

一种特殊的二叉树，满足其左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有的结点的数据域均大于根结点的数据域。

查找

1. 如果当前根结点root为空，查找失败，返回
2. 如果x等于根结点数据域root->data，查找成功
3. 如果x小于根结点数据域root->data，则往root->lchild递归查找
4. 如果x大于根结点数据域root->data，则往root->rchild递归查找

// 查找
void search(node* root, int x) {
    if(root == NULL) {
        return;
    }
    if(x == root->data) {
        printf("found\n");
    }else if(x < root->data) {
        search(root->lchild, x);
    }else {
        search(root->rchild, x);
    }
}

查找将会是从树根到查找结点的一条路径，故最坏复杂度是O(h)，其中h是二叉查找树的高度。

插入

插入在查找的基础上，若查找成功，说明已经存在，返回；若查找失败，说明该处就是插入的位置。时间复杂度也是O(h)。

// 插入 注意root前加引用&
void insert(node* &root, int x) {
    if(root == NULL) {
        root = newNode(x);
        return;
    }
    if(x == root->data) {
        return;
    }
    if(x < root->data) {
        insert(root->lchild, x);
    }else {
        insert(root->rchild, x);
    }
}

建立

从数组建立二叉查找树，就是依次插入结点的过程。

// 建立
node* createFromList(int list[], int n) {
    node* root = NULL;
    for(int i=0; i<n; i++) {
        insert(root, list[i]);
    }
    return root;
}

删除

前驱：比结点权值小的最大结点称为该结点的前驱。（从左子树根结点开始不断沿着rchild往下直到rchild为NULL时的结点）

后继：比结点权值大的最小结点称为该结点的后继。（从右子树根结点开始不断沿着lchild往下直到lchild为NULL时的结点）

删除某个结点(后需要保持bst性质)可以使用该结点的前驱覆盖该结点，然后删除前驱。（或者使用后继）

1. 若当前结点为NULL，说明不存在权值为x的结点，直接返回
2. 若当前结点权值为x，进入删除处理
   • 若当前结点不存在左右孩子，说明是叶子结点，直接删除
   • 若当前结点存在左孩子，那么在左子树中寻找前驱pre，然后让pre的数据覆盖root，然后删除pre
   • 若当前结点存在右孩子，那么在右子树中寻找后继next，然后让next的数据覆盖root，然后删除next
3. 若当前结点权值大于x，则在左子树中递归删除
4. 若当前结点权值小于x，则在右子树中递归删除

// 寻找以root为根结点的树中的最大权值结点
node* findMax(node* root) {
    while(root->rchild != NULL) {
        root = root->rchild;
    }
    return root;
}

// 寻找以root为根结点的树中的最小权值结点
node* findMin(node* root) {
    while(root->lchild != NULL) {
        root = root->lchild;
    }
    return root;
}

// 删除以root为根结点的树中权值为x的结点 注意root前加引用&
void delNode(node* &root, int x) {
    if(root == NULL) {   // 不存在x
        return;
    }
    if(root->data == x) {
        if(root->lchild == NULL && root->rchild == NULL) {   // x即为叶子结点，赋值NULL，其父结点便无法引用
            root = NULL;
        } else if(root->lchild != NULL) {   
            node* pre = findMax(root->lchild);   // 找前驱
            root->data = pre->data;
            delNode(root->lchild, pre->data);   // 在左子树中删除pre
        } else {
            node* next = findMin(root->rchild);   // 找后继
            root->data = next->data;
            delNode(root->rchild, next->data);
        }
    } else if(root->data > x) {
        delNode(root->lchild, x);
    } else {
        delNode(root->rchild, x);
    }
}

总是先删除前驱或后继容易导致左右子树高度不平衡，是二叉查找树退化成一条链。解决办法有二：一是交替删除前驱或后继，而是记录子树高度，总是优先删除较高的子树结点。

性质

对二叉查找树进行中序遍历，输出结果是有序的。

go版

package tree

//Node 结点定义
type Node struct {
    data   int
    lchild *Node
    rchild *Node
}

// BST 二叉查找树binarySearchTree
type BST struct {
    root  *Node
    count int
}

var i = 0

// 添加结点
func (node *Node) addNode(newNode *Node) {
    if node.data > newNode.data {
        if node.lchild == nil {
            node.lchild = newNode
        } else {
            node.lchild.addNode(newNode)
        }
    } else {
        if node.rchild == nil {
            node.rchild = newNode
        } else {
            node.rchild.addNode(newNode)
        }
    }
}

func (bst *BST) Add(data int) {
    var newNode Node
    newNode.data = data
    if bst.root == nil {
        bst.root = &newNode
    } else {
        bst.root.addNode(&newNode)
    }
    bst.count++
}

//中序遍历
func (node *Node) toArrayNode(datas []int) {
    if node.lchild != nil {
        node.lchild.toArrayNode(datas)
    }
    datas[i] = node.data
    i++
    if node.rchild != nil {
        node.rchild.toArrayNode(datas)
    }
}

func (bst *BST) ToArray() []int {
    if bst.root == nil {
        return nil
    }
    datas := make([]int, bst.count)
    bst.root.toArrayNode(datas)
    return datas
}

func (bst *BST) Size() int {
    return bst.count
}

package main

import (
    "algo/tree"
    "fmt"
)

func main() {
    var bst tree.BST
    bst.Add(5)
    bst.Add(11)
    bst.Add(8)
    bst.Add(9)
    bst.Add(1)
    bst.Add(3)
    bst.Add(20)
    fmt.Println(bst.Size())
    fmt.Println(bst.ToArray())
}

平衡二叉树(AVL树)

定义

一种特殊的二叉查找树，对任意结点，其左右子树的高度之差(称为该结点的平衡因子)的绝对值不超过1。

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

//AVL树结构定义
struct node {
    int data, height;   // height为当前子树高度
    node *lchild, *rchild;
};

// 新结点生成
node* newNode(int v) {
    node* Node = new node;
    Node->data = v;
    Node->height = 1;   // 结点高度初始为1
    Node->lchild = Node->rchild = NULL;
    return Node;
}

// 获取以root为根结点的子树的当前height
int getHeight(node* root) {
    if(root == NULL) {
        return 0;
    }
    return root->height;
}

// 计算root结点的平衡因子
int getBalanceFactor(node* root) {
    return getHeight(root->lchild) - getHeight(root->rchild);
}

// 更新root结点的height
void updateHeight(node* root) {
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}

// 查找
void search(node* root, int x) {
    if(root == NULL) {
        return;
    }
    if(x == root->data) {
        printf("found\n");
    }else if(x < root->data) {
        search(root->lchild, x);
    }else {
        search(root->rchild, x);
    }
}

// 左旋
void L(node* &root) {
    node* temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    // 记得更新结点高度
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

//右旋转(左旋里的left和right互换即可)
void R(node* &root) {
    node* temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

// 插入 注意root前加引用&
void insert(node* &root, int x) {
    if(root == NULL) {
        root = newNode(x);
        return;
    }
    if(x == root->data) {
        return;
    }
    if(x < root->data) {
        insert(root->lchild, x);
        updateHeight(root);   // 更新树高
        if(getBalanceFactor(root) == 2) {
            if(getBalanceFactor(root->lchild) == 1) {   // LL
                R(root);
            } else if(getBalanceFactor(root->lchild) == -1) {   // LR
                L(root->lchild);
                R(root);
            }
        }
    }else {
        insert(root->rchild, x);
        updateHeight(root);   // 更新树高
        if(getBalanceFactor(root) == -2) {
            if(getBalanceFactor(root->rchild) == -1) {   // RR
                L(root);
            } else if(getBalanceFactor(root->rchild) == 1) {   // RL
                R(root->rchild);
                L(root);
            }
        }
    }
}

// 建立
node* createFromList(int list[], int n) {
    node* root = NULL;
    for(int i=0; i<n; i++) {
        insert(root, list[i]);
    }
    return root;
}

// 层次遍历
void layerPrint(node *root) {
    queue<node*> q;
    q.push(root);
    while(!q.empty()) {
        node* top = q.front();
        q.pop();
        printf("%d ", top->data);
        if(top->lchild != NULL) {
            q.push(top->lchild);
        }
        if(top->rchild != NULL) {
            q.push(top->rchild);
        }
    }
}

int main() {
    int list[]={1, 2, 3, 4, 5, 6};
    int n=sizeof(list)/sizeof(list[0]);
    node* Node=createFromList(list, n);
    layerPrint(Node);
    return 0;
}

查找

同二叉查找树的查找操作

插入

二叉查找树的左旋(Left Rotation)

设根结点A的右子树为结点B，由二叉查找树的定义可知A的左子树的全部结点都比A小，B的右子树的全部结点都比B大，故这两个子树的相对位置不用变，左旋操作如下

1. 让B的左子树成为A的右子树
2. 让A成为B的左子树
3. 让B成为根结点

二叉查找树的右旋(Right Rotation)

与左旋相对，左旋的结果进行右旋即恢复到原始状态。右旋操作如下

1. 让A的右子树成为B的左子树
2. 让B成为A的右子树
3. 让A成为根结点

AVL树的插入

往一颗AVL树中插入一个结点(用二叉查找树的插入方式)，显然只有在从根结点到该插入结点的路径上的结点才可能发生平衡因子的变化，因此只需要对这条路径上的失衡结点进行调整。可以证明，只要把最靠近插入结点的失衡结点调整到正常，路径上所有结点就都会平衡。

假设靠近插入结点的失衡结点是A，显然它的平衡因子只可能是2或者-2，这两种情况完全是对称的。

当失衡因子是2，即左子树比右子树高度大2，以A为根结点的子树具有两种形态LL型和LR型。可知当A的左孩子平衡因子是1时为LL型，-1时为LR型。

当失衡因子是-2，即右子树比左子树高度大2，以A为根结点的子树具有两种形态RR型和RL型。可知当A的右孩子平衡因子是-1时为RR型，1时为RL型。

树型	判断条件	调整方法
LL	BF(root)=2,BF(root->lchild)=1	对root进行右旋
LR	BF(root)=2,BF(root->lchild)=-1	先对root->lchild进行左旋，再对root进行右旋
RR	BF(root)=-2,BF(root->Rchild)=-1	对root进行左旋
RL	BF(root)=-2,BF(root->lchild)=1	先对root->rchild进行右旋，再对root进行左旋

建立

在插入操作的基础上，AVL树的建立很简单，依次插入结点即可。

并查集

定义

并查集(Union Find Set)是一种维护集合的数据结构，支持下面两个操作

• 合并：合并两个集合
• 查找：判断两个元素是否在一个集合
  用数组实现

int father[N];

其中father[i]表示元素i的父亲结点，而父亲结点本身也是这个集合内的元素，例如father[1]=2表示元素1的父亲结点是元素2。若father[i]=i，说明元素i是该集合的根结点，对于同一个集合来说只存在一个根结点，且将其作为所属集合的标识。

初始化

令father[i]=i

查找根结点

递推或递归查找，直到满足father[i]==i

#include<cstdio>

const int maxn=20;
int father[maxn];

// 查找根结点
int findFather(int x) {
    if(x == father[x]) {
        return x;
    }
    return findFather(father[x]);
}

// 路径压缩
int findFatherPro(int x) {
    if(x == father[x]) {
        return x;
    }
    int fa = findFather(father[x]);
    father[x] = fa; // 将x的父结点直接赋值为根结点
    return fa;
}

// 合并集合
void Union(int a, int b) {
    int fa = findFather(a);
    int fb = findFather(b);
    if(fa != fb) {   // 不同的集合才能合并
        father[fa] = fb;
    }
}

int main() {
    return 0;
}

堆

定义

堆是一棵完全二叉树，树中的每个结点的值都不小于(不大于)其左右孩子结点的值，如果父亲结点的值大于等于孩子结点的值，那么称这样的堆为大顶堆；如果父亲结点的值小于等于孩子结点的值，那么称这样的堆为小顶堆。堆一般用于实现优先队列，以下说明以大顶堆为例。

大顶堆

#include<cstdio>
#include<vector>
using namespace std;

const int maxn=100;
int heap[maxn], n=10;

vector<int> vi;
// 向下调整法，low为欲调整结点数组下标，high一般为数组最后一个元素下标
void downAdjust(int low, int high) {
    int i=low;
    int j=i*2;   // j为i左孩子小标
    while(j<=high) {
        if(j+1<=high && heap[j+1]>heap[j]) {   // 右孩子存在且值大于左孩子，取右孩子值作为比较值
            j = j+1;
        }
        if(heap[i]<heap[j]) {
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
            i = j;
            j = i*2;
        } else {
            break;
        }
    }
}

// 向上调整法，low一般为1，high一般为欲调整元素下标
void upAdjust(int low, int high) {
    int i=high;
    int j=i/2;   // j为i的父结点
    while(j>=low) {
        if(heap[i]>heap[j]) {
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
            i = j;
            j = i/2;
        } else {
            break;
        }
    }
}

// 从n/2开始倒序遍历调整
void createHeap() {
    for(int i=n/2; i>=1; i--) {
        downAdjust(i, n);
    }
}

// 删除堆顶元素
void delTop() {
    heap[1] = heap[n--];
    downAdjust(1, n);
}

// 插入元素
void insert(int x) {
    heap[++n] = x;
    upAdjust(1, n);
}

// 堆排序直观法
void heapSort() {
    while(n>=1) {
        vi.push_back(heap[1]);
        delTop();
    }
}

// 堆排序节省空间法，结果从小到大
void heapSortPro() {
    for(int i=n; i>1; i--) {
        int temp = heap[1];
        heap[1] = heap[i];
        heap[i] = temp;
        downAdjust(1, i-1);
    }
}

int main() {
    int list[] = {85, 55, 82, 57, 68, 92, 99, 98, 66, 56};
    for(int i=1; i<=n; i++) {
        heap[i]=list[i-1];
    }
    createHeap();
    //delTop();
    //insert(88);
    //heapSortPro();
    for(int i=1; i<=n; i++) {
        printf("%d ", heap[i]);
    }
    // heapSort();
    // for(vector<int>::iterator it=vi.begin(); it != vi.end(); it++) {
    //     printf("%d ", *it);
    // }
    return 0;
}

go版

package heap

//向下调整法 low为欲调整结点下标，high为最后一个元素下标
func downAdjust(slice []int, low int, high int) {
    i := low
    j := i * 2 // 左孩子下标
    for j < high {
        if j+1 < high && slice[j+1] > slice[j] {
            j++
        }
        if slice[i] < slice[j] {
            temp := slice[i]
            slice[i] = slice[j]
            slice[j] = temp
            i = j
            j = i * 2
        } else {
            break
        }
    }
}

func New(slice []int) {
    size := len(slice)
    for i := size / 2; i >= 1; i-- {
        downAdjust(slice, i, size)
    }
}

package main

import (
    "algo/heap"
    "fmt"
)

func main() {
    slice := []int{-1, 85, 55, 82, 56, 68, 92, 99, 98, 66, 57} // 元素从下标1开始存贮
    heap.New(slice)
    fmt.Println(slice[1:])
}

小顶堆

#include<cstdio>
#include<vector>
using namespace std;

const int maxn=100;
int heap[maxn], n=10;

vector<int> vi;
// 向下调整法，low为欲调整结点数组下标，high一般为数组最后一个元素下标
void downAdjust(int low, int high) {
    int i=low;
    int j=i*2;   // j为i左孩子小标
    while(j<=high) {
        if(j+1<=high && heap[j+1]<heap[j]) {   //   与heapMax区别>
            j = j+1;
        }
        if(heap[i]>heap[j]) {   //   与heapMax区别<
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
            i = j;
            j = i*2;
        } else {
            break;
        }
    }
}

// 向上调整法，low一般为1，high一般为欲调整元素下标
void upAdjust(int low, int high) {
    int i=high;
    int j=i/2;   // j为i的父结点
    while(j>=low) {
        if(heap[i]<heap[j]) {   //   与heapMax区别>
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
            i = j;
            j = i/2;
        } else {
            break;
        }
    }
}

// 从n/2开始倒序遍历调整
void createHeap() {
    for(int i=n/2; i>=1; i--) {
        downAdjust(i, n);
    }
}

// 删除堆顶元素
void delTop() {
    heap[1] = heap[n--];
    downAdjust(1, n);
}

// 插入元素
void insert(int x) {
    heap[++n] = x;
    upAdjust(1, n);
}

// 堆排序直观法
void heapSort() {
    while(n>=1) {
        vi.push_back(heap[1]);
        delTop();
    }
}

// 堆排序节省空间法，结果从大到小
void heapSortPro() {
    for(int i=n; i>1; i--) {
        int temp = heap[1];
        heap[1] = heap[i];
        heap[i] = temp;
        downAdjust(1, i-1);
    }
}

int main() {
    int list[] = {85, 55, 82, 57, 68, 92, 99, 98, 66, 56};
    for(int i=1; i<=n; i++) {
        heap[i]=list[i-1];
    }
    createHeap();
    //delTop();
    insert(50);
    heapSortPro();
    for(int i=1; i<=n; i++) {
        printf("%d ", heap[i]);
    }
    // heapSort();
    // for(vector<int>::iterator it=vi.begin(); it != vi.end(); it++) {
    //     printf("%d ", *it);
    // }
    return 0;
}

实现

完全二叉树的存贮

对于完全二叉树，比较简单的实现方式是使用数组来存贮，按照完全二叉树的层次结构从上至下，从左至右，依次存入数组A(从数组下标1开始)。这样对于数组元素A[i]可知其左右孩子的位置为2i和2i+1，同时最后一个存在孩子的结点下标为n/2(n为数组最后一个元素下标，即完全二叉树结点总数)。

向下调整法

1. 当前结点V若存在孩子结点，且V的值小于孩子结点中的最大值，则交换V和孩子结点中的最大值
2. 交换完毕，让V重复步骤1，直至V的值大于其孩子结点值或其不存在孩子结点

向上调整法

当前结点与其父结点比较，若其值大于父结点值，则交换，反复比较直到到达堆顶或父结点值较大为止。

建堆过程

假设序列中元素个数是n，则可知最后一个存在孩子的结点下标为n/2，从该下标开始倒序遍历，对于遍历中对每一个i，在[i,n]范围内使用向下调整法。时间复杂度为O(n)。

删除堆顶元素

用最后一个元素覆盖堆顶元素，然后使用向下调整法(注意n--)

添加元素

把要添加的元素放到数组最后，使用向上调整法

堆排序

堆排序是指使用堆结构对一个序列进行排序。

堆建立完毕后，堆排序的直观思路是反复删除堆顶元素，直至堆空。（删除的元素需要另开空间保存）

另一种节省空间的方法是倒序遍历数组，当访问到第i号位，将其与堆顶互换，然后在[1, i-1]范围内进行向下调整。

哈夫曼树

定义

路径长度

指从根结点出发到达该结点所经过的边数。

带权路径长度

结点的的权重值乘以其路径长度值。

树的带权路径长度(Weighted Path Length of Tree-WPL)等于它所有叶子结点的带权路径长度和。

哈夫曼树

带权路径长度最小的二叉树成为哈夫曼树，也称最优二叉树。显然，对于同一组叶子结点来说，哈夫曼树可能不是唯一的，但是最小带权路径长度一定是唯一的。

建立

1. 初始状态下共有n个结点（结点的权值分别是给定的n个树），将他们视作n棵只有一个结点的树
2. 合并其中根结点权值最小的两棵树，权值和作为父结点的权值，这样树的就减少一棵
3. 重复步骤2，直至剩一棵树为止，这棵树就是哈夫曼树