二叉树原理及编程详解(一)完全二叉树|堆排序|遍历|重建

╰+攻爆jí腚メ 2021-11-19 12:12 190阅读 0赞

**目录**

一、二叉树基础概念

1.1 基础概念：

1.2 二叉树的性质

二、二叉树的遍历

2.1 三种遍历方法

2.2 二叉树的构建

2.3 重建方法及解析

2.4 重建二叉树的代码实现

c++重建二叉树

python重建二叉树

三、二叉树编程汇总

3.1 树的子结构

c++树的子结构

3.2 镜像二叉树

c++镜像二叉树

3.3 按层打印二叉树

c++按层打印二叉树

3.4 判断排序二叉树后序遍历

c++判断排序二叉树后序遍历

3.5 二叉树的深度

c++二叉树深度

3.6 平衡二叉树

c++平衡二叉树

3.7 对称二叉树

c++对称二叉树

四、堆排序

4.1 大顶堆与小顶堆

4.2 基本思想与步骤

步骤一、构造初始堆

步骤二、顶端与末尾交换

4.3 代码

创建堆

调整当前非叶子节点

完整代码

--------------------

# 一、二叉树基础概念 #

## 1.1 基础概念： ##

*  子树：非空二叉树节点数N>1时候，除了根节点之外的结点可以分为互不相交的有限集合，每个集合本身又是一颗二叉树。
 *  结点的度：结点拥有子树的数量。
 *  叶子结点，也称为终端结点：度为0的结点
 *  非终端结点，也称为分支结点：度不为0的结点
 *  满二叉树：深度为k的二叉树具有 2^k-1 个结点
 *  **完全二叉树**(堆)：完全二叉树是效率很高的数据结构。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一 一对应时称之为完全二叉树。（堆即是完全二叉树的数组对象）
 *  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70][]

结点 node，不是节点。

## 1.2 二叉树的性质 ##

*  性质一：二叉树的第i层上至多有2^(i-1)个节点。
 *  性质二：深度为k的二叉树，至多有 2^k-1 个节点
 *  性质三：二叉树若终端结点为n0，度为2的节点为n2，则 n0=n2+1

前两个容易证明，第三个性质，所有结点为n，度为1的结点个数为n1，度为2的结点个数n2

n=n0+n1+n2

设置B为分支的个数，即两个结点之间的连接情况，B=n1+2×n2，除了根结点之外，所有结点均有分支进入，n=B+1

结合起来即为： n0=n2+1

*  性质四：n结点的完全二叉树的深度为 floor\[ log2(n) \] +1
 *  性质五：当前节点编号为n，则其左孩子结点为 2×n+1，右 2×n+2

# 二、二叉树的遍历 #

## 2.1 三种遍历方法 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 1][]

前序，中序，后续是根据根节点出现的位置来命名的。

*  前序：根，左，右
 *  中序：左，根，右
 *  后续：左，右，根

宽度优先遍历：

一层一层往下遍历，10，6，14，4，8，12，16

## 2.2 二叉树的构建 ##

设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）？  
正确答案: A

*  BADC
 *  BCDA
 *  CDAB
 *  CBDA

之前感觉有点难，因为没弄明白遍历是怎么进行的，弄明白遍历的进行即可看懂。

## 2.3 重建方法及解析 ##

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。做这种题需要有递归的思想，并不难。理论推导：

前序第一个是根节点的数值，必然是1，中序的时候左边为1左边的值，右边为1右边的值。 然后在分开的左子树和右子树之中重复进行此步骤。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 2][]

剩下的步骤递归即可完成。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 3][]

## 2.4 重建二叉树的代码实现 ##

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

### c++重建二叉树 ###

关于这个，依然是真的vector的操作需要知道。尾部添加变量的函数是push\_back.

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
            int length=pre.size();
            if(length==0)return NULL;
            //root node
            TreeNode* root=new TreeNode(pre[0]);
            vector<int> left_pre,left_vin,right_pre,right_vin;
            //find root node in vin
            int root_loc_vin;
            for( root_loc_vin=0;root_loc_vin<length;root_loc_vin++){
                if (vin[root_loc_vin]==pre[0])break;
            }
            //split vin,pre to left
            for(int idx_left_vin=0;idx_left_vin<root_loc_vin;idx_left_vin++){
                left_vin.push_back(vin[idx_left_vin]);
                left_pre.push_back(pre[idx_left_vin+1]);
            }
            //split vin,pre to right
            for(int idx_right_vin=root_loc_vin+1;idx_right_vin<length;idx_right_vin++){
                right_vin.push_back(vin[idx_right_vin]);
                right_pre.push_back(pre[idx_right_vin]);
            }
            root->left=reConstructBinaryTree(left_pre,left_vin);
            root->right=reConstructBinaryTree(right_pre,right_vin);
            return root;
        }
    };

有几点需要注意：

指针类型的函数，如果直接返回，需要返回NULL，

创建新的节点的话需要用指针=new struct(构造函数)

vector的push\_back()函数，复习前面的insert()函数，删除用pop\_back()函数

### python重建二叉树 ###

# class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回构造的TreeNode根节点
        def reConstructBinaryTree(self, pre, tin):
            # write code here
            if(len(pre)==0):
                return None
            root=TreeNode(pre[0])
            # find root loc in tin
            idx_root_tin=tin.index(pre[0])
            root.left=self.reConstructBinaryTree(pre[1:idx_root_tin+1],tin[0:idx_root_tin])
            root.right=self.reConstructBinaryTree(pre[idx_root_tin+1:],tin[idx_root_tin+1:])
            return root

需要了解python的语法，可看[python项目应用实例(一)常见运算|维度|基本元素|基本语法|函数 ][python_]中的八

python中的分片与步长 [https://www.cnblogs.com/kuqs/p/6541723.html][https_www.cnblogs.com_kuqs_p_6541723.html]

分片的时候，\[开始位置：结束位置+1\]这个要搞清楚

# 三、二叉树编程汇总 #

## 3.1 树的子结构 ##

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

递归非常重要，并且可能存在递归的嵌套。这种题需要反复做，反复体会。

### c++树的子结构 ###

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        bool RootHasSubTree(TreeNode* pRoot1, TreeNode* pRoot2){
            if(pRoot2==NULL)return true;
            if(pRoot1==NULL)return false;
            if(pRoot1->val==pRoot2->val)return RootHasSubTree(pRoot1->left,pRoot2->left)&&RootHasSubTree(pRoot1->right,pRoot2->right);
            else return false;
        }
        bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
        {
            if(pRoot1==NULL||pRoot2==NULL)return false;
            bool result=false;
            if(pRoot1->val==pRoot2->val)result=RootHasSubTree(pRoot1,pRoot2);
            if(!result)result=HasSubtree(pRoot1->left,pRoot2);
            if(!result)result=HasSubtree(pRoot1->right,pRoot2);
            return result;
        }
    };

## 3.2 镜像二叉树 ##

对于二叉树问题，掌握递归则基本掌握了二叉树的解法。

操作给定的二叉树，将其变换为源二叉树的镜像。（数的子节点也要倒顺序）

### c++镜像二叉树 ###

跟先递归调用mirror，再进行左右交换一样。

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        void Mirror(TreeNode *pRoot) {
            if(pRoot==NULL)return;
            TreeNode * temp=pRoot->left;
            pRoot->left=pRoot->right;
            pRoot->right=temp;
            Mirror(pRoot->left);
            Mirror(pRoot->right);
            return;
        }
    };

## 3.3 按层打印二叉树 ##

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解析：这叫宽度优先遍历。

### c++按层打印二叉树 ###

需要掌握queue的操作：[https://www.cnblogs.com/danielStudy/p/6726491.html][https_www.cnblogs.com_danielStudy_p_6726491.html]

注意queue的用法与stack类似。也是.push()与.pop()，但是第一个元素是.front()，而stack的顶元素为.top()

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        vector<int> PrintFromTopToBottom(TreeNode* root) {
            vector<int> value_queue;
            if(root==NULL)return value_queue;
            queue<TreeNode*> node_que;
            node_que.push(root);
            while(!node_que.empty()){
                TreeNode* current_node=node_que.front();
                value_queue.push_back(current_node->val);
                if(current_node->left!=NULL)node_que.push(current_node->left);
                if(current_node->right!=NULL)node_que.push(current_node->right);
                node_que.pop();
            }
            return value_queue;
        }
    };

### 按层打印成多行 ###

如果是按层打印二叉树的，且打印成多行：

class Solution {
    public:
    	vector<vector<int> > Print(TreeNode* pRoot) {
    		vector<vector<int> > value;
    		if (pRoot == NULL)return value;
    		queue<TreeNode*> node_queue;
    		node_queue.push(pRoot);
    		int line_size = 1;
    		while (node_queue.size()){
    			vector<int> line_value;
    			line_size = node_queue.size();
    			while (line_size>0){
    				if (node_queue.front()->left != NULL)node_queue.push(node_queue.front()->left);
    				if (node_queue.front()->right != NULL)node_queue.push(node_queue.front()->right);
    				line_value.push_back(node_queue.front()->val);
    				node_queue.pop();
    				line_size--;
    			}
    			value.push_back(line_value);
    		}
    		return value;
    	}
    };

### 之字形打印二叉树 ###

构建两个stack，在两个stack之间交替。

struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    		val(x), left(NULL), right(NULL) {
    	}
    };
    
    class Solution {
    public:
    	vector<vector<int>> Print(TreeNode* pRoot) {
    		vector<vector<int>> z_value;
    		if (pRoot == NULL)return z_value;
    		stack<TreeNode*> stack_1;
    		stack_1.push(pRoot);
    		stack<TreeNode*> stack_2;
    		
    		while (!stack_1.empty() || !stack_2.empty()){
    			if (stack_2.empty() && !stack_1.empty()){
    				vector<int> line_value;
    				while (!stack_1.empty()){
    					if (stack_1.top()->left != NULL)
    						stack_2.push(stack_1.top()->left);
    					if (stack_1.top()->right != NULL)
    						stack_2.push(stack_1.top()->right);
    					line_value.push_back(stack_1.top()->val);
    					stack_1.pop();
    				}
    				z_value.push_back(line_value);
    				line_value.clear();
    			}
    			if (stack_1.empty() && !stack_2.empty()){
    				vector<int> line_value;
    				while (!stack_2.empty()){
    					if (stack_2.top()->right != NULL)
    						stack_1.push(stack_2.top()->right);
    					if (stack_2.top()->left != NULL)
    						stack_1.push(stack_2.top()->left);
    					line_value.push_back(stack_2.top()->val);
    					stack_2.pop();
    				}
    				z_value.push_back(line_value);
    				line_value.clear();
    			}
    		}
    		return z_value;
    	}
    };
    
    int main(){
    	int a = 1, b = 2, c = 3;
    	TreeNode* root = new struct TreeNode(a);
    	TreeNode* left=new struct TreeNode(b);
    	TreeNode* right = new struct TreeNode(c);
    	root->left = left;
    	root->right = right;
    
    	Solution sloution_1;
    
    	vector<vector<int>> z_print = sloution_1.Print(root);
    	return 0;
    }

## 3.4 判断排序二叉树后序遍历 ##

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解析：二叉树可以用于排序，并且其中有很多知识点。排序二叉树的值，后序遍历，则一定是，顺序一定是\{小值，大值，中间值\}

任意一个节点，只要其左边的值顺序一定是\{比它小，比它大\}

### c++判断排序二叉树后序遍历 ###

如果掌握了前面的知识点，则这个可以很快做出来。

class Solution {
    public:
        bool VerifySquenceOfBST(vector<int> sequence) {
            int sequence_size=sequence.size();
            if(sequence_size<1)return false;
            for(int seq_idx=sequence_size-1;seq_idx>0;seq_idx--){
                int compare_idx=0;
                while(sequence[compare_idx]<sequence[seq_idx])compare_idx++;
                while(sequence[compare_idx]>sequence[seq_idx])compare_idx++;
                if(compare_idx!=seq_idx)return false;
            }
            return true;
        }
    };

## 3.5 二叉树的深度 ##

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解析：基本上，二叉树的题，都需要运用递归，思路对的话，代码量并不大。

### c++二叉树深度 ###

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        int TreeDepth(TreeNode* pRoot)
        {
            if(pRoot==NULL)return 0;
            int left_depth=TreeDepth(pRoot->left);
            int right_depth=TreeDepth(pRoot->right);
            if(left_depth>right_depth)return left_depth+1;
            else return right_depth+1;
        }
    };

## 3.6 平衡二叉树 ##

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解析：平衡二叉树的左右节点深度差值不能超过1.

### c++平衡二叉树 ###

直接算出深度即可。abs表示绝对值函数，可以直接用。直接套用上题深度的测试。写法上可以更高明一点。

class Solution {
    public:
        int tree_depth(TreeNode* pRoot){
            if(pRoot==NULL)return 0;
            int left_depth=tree_depth(pRoot->left);
            int right_depth=tree_depth(pRoot->right);
            if(left_depth>right_depth)return left_depth+1;
            else return right_depth+1;
        }
        bool IsBalanced_Solution(TreeNode* pRoot) {
            if(pRoot==NULL)return true;
            if(abs(tree_depth(pRoot->left)-tree_depth(pRoot->right))>1)return false;
            else return true;
        }
    };

选择结构的写法可以如下：

class Solution {
    public:
        int tree_depth(TreeNode* pRoot){
            if(pRoot==NULL)return 0;
            int left_depth=tree_depth(pRoot->left);
            int right_depth=tree_depth(pRoot->right);
            return (left_depth>right_depth)? left_depth+1:right_depth+1;
        }
        bool IsBalanced_Solution(TreeNode* pRoot) {
            if(pRoot==NULL)return true;
            return (abs(tree_depth(pRoot->left)-tree_depth(pRoot->right))>1)? false:true;
        }
    };

## 3.7 对称二叉树 ##

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解析：原题给出的函数接口，只有一个节点，bool isSymmetrical(TreeNode\* pRoot)，并不利于递归调用，可以多设一个函数接口实现调用：

### c++对称二叉树 ###

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
    class Solution {
    public:
        bool isSymmetrical(TreeNode* pRoot)
        {
            if(pRoot==NULL)return true;
            return isSymmetrical_node(pRoot->left,pRoot->right);
        }
        bool isSymmetrical_node(TreeNode* pLeft,TreeNode* pRight){
            if(pLeft==NULL&&pRight==NULL)return true;
            else if(pLeft==NULL||pRight==NULL)return false;
            if(pLeft->val==pRight->val)
                return isSymmetrical_node(pLeft->right,pRight->left)&&isSymmetrical_node(pLeft->left,pRight->right);
            else return false;
        }
    };

## 3.8 和为某一值的路径 ##

[https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=3&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking][https_www.nowcoder.com_practice_b736e784e3e34731af99065031301bca_tpId_13_tqId_11177_tPage_2_rp_3_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking]

从根结点到叶子节点的路径，和为某一值的路径：

（题干中有提到，数组内部元素更多的放前面，但是这个代码中没有，oj可以通过。）

class Solution {
    public:
    	vector<vector<int>> paths;
    	vector<int> temp_path;
    	vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
    		if (root == NULL)return paths;
    		temp_path.push_back(root->val);
    		if (expectNumber == root->val && root->left == NULL&&root->right == NULL){
    			paths.push_back(temp_path);
    		}
    		FindPath(root->left, expectNumber - root->val);
    		FindPath(root->right, expectNumber - root->val);
    		if (!temp_path.empty())temp_path.pop_back();
    		return paths;
    	}
    };

上面那个代码并不严谨，没有满足条件，数组需要再加一个判断，用insert函数来实现插入即可：

class Solution {
    public:
    	vector<vector<int> >paths;
    	vector<int> temp_path;
    	vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
    		if (root == NULL)return paths;
    		temp_path.push_back(root->val);
    		if (root->val == expectNumber && root->left == NULL && root->right == NULL){
    			if (paths.size() == 0)paths.push_back(temp_path);
    			else{
    				for (int idx = 0; idx < paths.size(); idx++){
    					if (temp_path.size()>paths[idx].size()){
    						paths.insert(paths.begin() + idx, temp_path);
    						break;
    					}
    				}
    			}
    		}
    		FindPath(root->right, expectNumber - root->val);
    		FindPath(root->left, expectNumber - root->val);
    
    		temp_path.pop_back();
    		return paths;
    	}
    };

# 四、堆排序 #

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列\{k1,k2,…,kn\}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

树形选择排序方法尚有辅助存储空间较多、和“最大值”进行多余比较等缺点。为了弥补，威洛姆斯（J. willioms）在1964年提出了另一种形式的[选择排序][Link 1]——[堆排序][Link 2]。

[https://www.cnblogs.com/chengxiao/p/6129630.html][https_www.cnblogs.com_chengxiao_p_6129630.html]

堆排序是利用**堆**这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是**不稳定排序**。首先简单了解下堆结构。

堆排序运用完全二叉树的性质，将二叉树的节点地址编号为地址，不用构建带有指针的二叉树，只用数组即可实现二叉树。

为什么不稳定排序：举一个反例即可，两个叶子节点上的数相同，但是叶子节点有可能进行swap，也有可能不进行swap，就可能无法保持稳定。

## 4.1 大顶堆与小顶堆 ##

排序中的堆与队列和程序中的堆与栈不一样，注意区分。

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 4][]

注意只需要父节点大于子节点，并不需要子节点之间进行排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 5][]

## 4.2 基本思想与步骤 ##

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

再简单总结下堆排序的基本思路：

**a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;**

**　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;**

**　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。**

### 步骤一、构造初始堆 ###

将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。容易理解，大顶堆在交换之后最后的元素最大，小顶堆在交换之后最后的元素最小。

a.假设给定无序序列结构如下

![aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5MjAzODY1MS05MzQzMjc2NDcucG5n][]

此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。（注意关于堆的性质，有一个性质是，第一个非叶子节点的编号=**length/2 -1**）

![aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5MjIwOTQzMy0yNzAzNzkyMzYucG5n][]

找到第二个非叶节点4，由于\[4,9,8\]中9元素最大，4和9交换。(堆之中是三个数字进行比较)

![aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5Mjg1NDYzNi0xODIzNTg1MjYwLnBuZw][]

这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6。

![aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5MzM0Nzg4Ni0xMTQyMTk0NDExLnBuZw][]

此时，我们就将一个无需序列构造成了一个大顶堆。

### 步骤二、顶端与末尾交换 ###

顶端与末尾元素交换之后，迭代进行步骤一

将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

![aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5NDIwNzYyMC0xNDU1MTUzMzQyLnBuZw][]

b.重新调整结构，使其继续满足堆定义

![aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxODE1MzExMDQ5NS0xMjgwMzg4NzI4LnBuZw][]

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

![aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxODE1MjkyOTMzOS0xMTE0OTgzMjIyLnBuZw][]

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

![aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxODE1MjM0ODIyOS05MzU2NTQ4MzAucG5n][]

## 4.3 代码 ##

[https://www.cnblogs.com/AlgrithmsRookie/p/5896603.html][https_www.cnblogs.com_AlgrithmsRookie_p_5896603.html]

### 创建堆 ###

此为创建大顶堆的代码，这种遍历是自底向顶的遍历

void make_heap(int *a, int len)
     {
        for(int i =  (len-1)/2; i >= 0; --i)    //遍历每个 非叶子节点
                      adjust_heap(a, i, len);//不用考虑那么多， 用面向对象的思乡去考虑，   
     }                                    //这个函数的作用就是用来使当前节点的子树符合堆的规律

### 调整当前非叶子节点 ###

当前非叶子节点构建大顶堆，

void adjust_heap(int* a, int node, int size)
    {
            int left = 2*node + 1;
            int right = 2*node + 2;  
            int max = node;
            if( left < size && a[left] > a[max])    
                    max = left;
            if( right < size && a[right] > a[max])
                    max = right;
            if(max != node)
            {   
                    swap( a[max], a[node]);    //交换节点
                    adjust_heap(a, max, size);     //递归
            }                     
    }

最后的递归表示，如果node与max的值交换之后，新的a\[max\]可能比它的两个儿子小，即管不住它的两个儿子，因此需要继续递归。

同时，考虑到如果node为叶子节点，则left和right<size这个判断就能保证了。

### 完整代码 ###

#include <iostream>
    using namespace std;
     
    void adjust_heap(int* a, int node, int size)
    {
            int left = 2*node + 1;
            int right = 2*node + 2;
            int max = node;
            if( left < size && a[left] > a[max])
                    max = left;
            if( right < size && a[right] > a[max])
                    max = right;
            if(max != node)
            {
                    swap( a[max], a[node]);
                    adjust_heap(a, max, size);
            }
    }
     
    void heap_sort(int* a, int len)
    {
            for(int i = len/2 -1; i >= 0; --i)
                    adjust_heap(a, i, len);
     
            for(int i = len - 1; i >= 0; i--)
            {
                    swap(a[0], a[i]);           // 将当前最大的放置到数组末尾
                    adjust_heap(a, 0 , i);              // 将未完成排序的部分继续进行堆排序
            }
    }
     
    int main()
    {
     
            int a[10] = {3, 2, 7, 4, 2, -999, -21, 99, 0, 9  };
            int len= sizeof(a) / sizeof(int);
     
            for(int i = 0; i < len; ++i)
                    cout << a[i] << ' ';
            cout << endl;
     
            heap_sort(a, len);
     
            for(int i = 0; i < len; ++i)
                    cout << a[i] << ' ';
            cout << endl;
     
            return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70]: /images/20211119/f18095a4216042fd8f5ce204069945cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 1]: /images/20211119/7f85b91159404e758907c8d63fb45bf9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 2]: /images/20211119/a687e352bab94a1487e7ea56ae2a9d1c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 3]: /images/20211119/4b234cd193a542d2ad52218d147a6473.png
[python_]: https://blog.csdn.net/weixin_36474809/article/details/88101294
[https_www.cnblogs.com_kuqs_p_6541723.html]: https://www.cnblogs.com/kuqs/p/6541723.html
[https_www.cnblogs.com_danielStudy_p_6726491.html]: https://www.cnblogs.com/danielStudy/p/6726491.html
[https_www.nowcoder.com_practice_b736e784e3e34731af99065031301bca_tpId_13_tqId_11177_tPage_2_rp_3_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking]: https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=3&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
[Link 1]: https://baike.baidu.com/item/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/9762418
[Link 2]: https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F/2840151
[https_www.cnblogs.com_chengxiao_p_6129630.html]: https://www.cnblogs.com/chengxiao/p/6129630.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 4]: /images/20211119/187a038ba72a409aa2a8cdd6cbab6803.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 5]: /images/20211119/bb9afe780a124a4f97c861a7492cda98.png
[aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5MjAzODY1MS05MzQzMjc2NDcucG5n]: /images/20211119/4a89ca5a3b574f758947d2fc58c9220d.png
[aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5MjIwOTQzMy0yNzAzNzkyMzYucG5n]: /images/20211119/429182277df849f6839a07bac5f2a6f9.png
[aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5Mjg1NDYzNi0xODIzNTg1MjYwLnBuZw]: /images/20211119/f8102720df814ba19faa0d1551002781.png
[aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5MzM0Nzg4Ni0xMTQyMTk0NDExLnBuZw]: /images/20211119/abb7e87f097e45efa4660dfb37c183e5.png
[aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxNzE5NDIwNzYyMC0xNDU1MTUzMzQyLnBuZw]: /images/20211119/b35f35d0bed24ca2bda1850cf434e4f0.png
[aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxODE1MzExMDQ5NS0xMjgwMzg4NzI4LnBuZw]: /images/20211119/cc2fd4d86d884b05bdb90941eb7fbdf6.png
[aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxODE1MjkyOTMzOS0xMTE0OTgzMjIyLnBuZw]: /images/20211119/ca919e7354c04915aade1f29773bd559.png
[aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTAyNDU1NS8yMDE2MTIvMTAyNDU1NS0yMDE2MTIxODE1MjM0ODIyOS05MzU2NTQ4MzAucG5n]: /images/20211119/465274bbe85145e2ae4368630e0212e9.png
[https_www.cnblogs.com_AlgrithmsRookie_p_5896603.html]: https://www.cnblogs.com/AlgrithmsRookie/p/5896603.html