完全二叉树与堆C++代码及应用

堆的定义

堆其实就是一棵完全二叉树（若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边），定义为：具有n个元素的序列（h1,h2,...hn），当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)时称之为堆。

大顶堆

堆顶元素（即第一个元素）为最大项，并且（hi>=h2i,hi>=h2i+1），通俗地说父节点比子节点大。

小顶堆

堆顶元素为最小项，并且（hi<=h2i,hi<=2i+1），父节点比子节点小。

堆的性质

当前节点的序号为index，其左右两个自节点的序号为index*2和index*2+1，其父节点的序号为int(index/2);

满二叉树

一棵深度为k，且有 2k+1−1 个节点的二叉树，称为满二叉树（Full Binary Tree）。这种树的特点是每一层上的节点数都是最大节点数。

完全二叉树

而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。高度（深度）: 即层数k，注意【根】定义为height(root)=0。

完全二叉树的性质

具有n个节点的完全二叉树的深度为 k=log2n 。
【满二叉树】i层的节点数目为：2i
【满二叉树】节点总数和深度的关系：n=∑ki=02i=2k+1−1
【完全二叉树】最后一层的节点数为：n−(2k−1)=n+1−2k （因为除最后一层外，为【满二叉树】）
【完全二叉树】左子树的节点数为（总节点为n）：l(n)={n−2k−1,2k−1,n+1−2k≤2k−1因为最后一层全部都在左子树，右子树为【满二叉树】高度为 k-2n+1−2k>2k−1因为左子树为满二叉树，高度为k-1

【完全二叉树】右子树： r(n)=n−l(n)

完全二叉树层次遍历转后序遍历（不构造树）

从1开始

void toPost(int index){

if(index > n)return;

toPost(index * 2);

toPost(index * 2 + 1);

printf("%d%s", tree[index], index == 1?"\n":" ");

}

PAT 甲级 1147 Heaps （30 分）

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))

Your job is to tell if a given complete binary tree is a heap.

Input Specification

Each input file contains one test case. For each case, the first line gives two positive integers: M ( $\leq$ 100), the number of trees to be tested; and N (1 $<$ N $\leq$ 1,000), the number of keys in each tree, respectively. Then M lines follow, each contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

Output Specification

For each given tree, print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all. Then in the next line print the tree's postorder traversal sequence. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line.

Sample Input

3 8

98 72 86 60 65 12 23 50

8 38 25 58 52 82 70 60

10 28 15 12 34 9 8 56

Sample Output

Max Heap

50 60 65 72 12 23 86 98

Min Heap

60 58 52 38 82 70 25 8

Not Heap

56 12 34 28 9 8 15 10

作者: CHEN, Yue

单位: 浙江大学

时间限制: 200 ms

内存限制: 64 MB

代码长度限制: 16 KB

代码

#include<iostream>

#include<vector>

#include<cstdio>

using namespace std;

int n;

vector<int> tree(10001);

void toPost(int index){

if(index > n)return;

toPost(index * 2);

toPost(index * 2 + 1);

printf("%d%s", tree[index], index == 1?"\n":" ");

}

int main(){

int t;

cin>>t>>n;

while(t--){

bool isMin = true, isMax = true;

for(int i = 1; i <= n; i++)scanf("%d", &tree[i]);

for(int i = 2; i <= n; i++){

if(tree[i/2] < tree[i]) isMax = false;

if(tree[i/2] > tree[i]) isMin = false;

}

if(isMin)cout<<"Min Heap"<<endl;

if(isMax)cout<<"Max Heap"<<endl;

if(!isMin&&!isMax)cout<<"Not Heap"<<endl;

toPost(1);

}

return 0;

}

PAT 甲级 1155 Heap Paths （30 分）

One thing for sure is that all the keys along any path from the root to a leaf in a max/min heap must be in non-increasing/non-decreasing order.

Your job is to check every path in a given complete binary tree, in order to tell if it is a heap or not.

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer $N$ ( $1 < N \leq 1, 000$ ), the number of keys in the tree. Then the next line contains $N$ distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

Output Specification

For each given tree, first print all the paths from the root to the leaves. Each path occupies a line, with all the numbers separated by a space, and no extra space at the beginning or the end of the line. The paths must be printed in the following order: for each node in the tree, all the paths in its right subtree must be printed before those in its left subtree.

Finally print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all.

Sample Input 1

98 72 86 60 65 12 23 50

Sample Output 1

98 86 23

98 86 12

98 72 65

98 72 60 50

Max Heap

Sample Input 2

8 38 25 58 52 82 70 60

Sample Output 2

8 25 70

8 25 82

8 38 52

8 38 58 60

Min Heap

Sample Input 3

10 28 15 12 34 9 8 56

Sample Output 3

10 15 8

10 15 9

10 28 34

10 28 12 56

Not Heap

作者: 陈越

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

代码

#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

int n;
vector<int> tree(10001);
vector<int> v;

void dfs(int index) {
    if (index * 2 > n && index * 2 + 1 > n) {//满足此条件的为叶子节点
        if (index <= n) {//对只有左叶节点没有右叶节点的点，与最后一个节点有关
            for (int i = 0; i < v.size(); i++)
                printf("%d%s", v[i], i != v.size() - 1 ? " " : "\n");
        }
    } else {
        v.push_back(tree[index * 2 + 1]);
        dfs(index * 2 + 1);
        v.pop_back();
        v.push_back(tree[index * 2]);
        dfs(index * 2);
        v.pop_back();
    }
}

int main(){

cin>>n;
    bool isMin = true, isMax = true;
    for(int i = 1; i <= n; i++)scanf("%d", &tree[i]);
    v.push_back(tree[1]);
    dfs(1);
    for(int i = 2; i <= n; i++){
        if(tree[i/2] < tree[i]) isMax = false;
        if(tree[i/2] > tree[i]) isMin = false;
    }

if(isMin)cout<<"Min Heap"<<endl;
    if(isMax)cout<<"Max Heap"<<endl;
    if(!isMin&&!isMax)cout<<"Not Heap"<<endl;
    return 0;
}

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

int n;

vector<int> tree(10001);

vector<int> v;

void dfs(int index) {

if (index * 2 > n && index * 2 + 1 > n) {//满足此条件的为叶子节点

if (index <= n) {//对只有左叶节点没有右叶节点的点，与最后一个节点有关

for (int i = 0; i < v.size(); i++)

printf("%d%s", v[i], i != v.size() - 1 ? " " : "\n");

}

} else {

v.push_back(tree[index * 2 + 1]);

dfs(index * 2 + 1);

v.pop_back();

v.push_back(tree[index * 2]);

dfs(index * 2);

v.pop_back();

}

int main(){

cin>>n;

bool isMin = true, isMax = true;

for(int i = 1; i <= n; i++)scanf("%d", &tree[i]);

v.push_back(tree[1]);

dfs(1);

for(int i = 2; i <= n; i++){

if(tree[i/2] < tree[i]) isMax = false;

if(tree[i/2] > tree[i]) isMin = false;

}

if(isMin)cout<<"Min Heap"<<endl;

if(isMax)cout<<"Max Heap"<<endl;

if(!isMin&&!isMax)cout<<"Not Heap"<<endl;

return 0;

}

完全二叉树与堆C++代码及应用

堆的定义

大顶堆

小顶堆

堆的性质

满二叉树

完全二叉树

完全二叉树的性质

完全二叉树层次遍历转后序遍历（不构造树）

PAT 甲级 1147 Heaps （30 分）

Input Specification

Output Specification

Sample Input

Sample Output

代码

PAT 甲级 1155 Heap Paths （30 分）

Input Specification

Output Specification

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

大模型中的RepE表征工程

大模型也是一种优化器（LLM as Optimizer）

全栈开发与快速部署Demo

学术idea自动发现与生成

自回归语言模型（language model）Python实现

粉丝期待的三体电影宇宙（近四十部电影与电视剧集）

基于历史对比学习的时序知识图谱推理

泰拉瑞亚Terriaria快速部署Linux服务器

iPad生产力指南——编程

DeepScience：学术趋势预测与分析

留下评论取消回复

堆的定义

大顶堆

小顶堆

堆的性质

满二叉树

完全二叉树

完全二叉树的性质

完全二叉树层次遍历转后序遍历（不构造树）

PAT 甲级 1147 Heaps （30 分）

Input Specification

Output Specification

Sample Input

Sample Output

代码

PAT 甲级 1155 Heap Paths （30 分）

Input Specification

Output Specification

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

相关文章

留下评论取消回复