C++ :

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int maxn = 30;
bool isRoot[maxn];  // 结点是否是根结点
struct Node {
    int data;
    int left, right;    // 左孩子和右孩子的下标
} node[maxn];   // 二叉树结点静态数组
int Heap[maxn];
// input函数输入数据
int input() {
    char id[3];
    scanf("%s", id);    // 输入结点编号
    if(id[0] == '-') {
        return -1;      // 如果是'-',说明是空结点,返回-1
    } else {
        if(strlen(id) == 1) return id[0] - '0';     // 编号小于10
        else return (id[0] - '0') * 10 + (id[1] - '0');     // 编号大于等于10
    }
}
// findRoot函数找到根结点编号
int findRoot(int n) {
    for(int i = 1; i <= n; i++) {
        if(isRoot[i]) {     // isRoot为true时直接返回根结点编号i
            return i;
        }
    }
}
int numNotBalanced = 0;
bool isAVL(int root, int &height) {
    if(root == -1) {
        height = 0;
        return true;
    }
    int leftH, rightH;
    bool isLeftAVL = isAVL(node[root].left, leftH);
    bool isRightAVL = isAVL(node[root].right, rightH);
    height = max(leftH, rightH) + 1;
    bool isBalanced = abs(leftH - rightH) <= 1;
    if(!isBalanced) numNotBalanced++;
    return isLeftAVL && isRightAVL && isBalanced;
}
int lastFull = 0;
// BFS函数判断完全二叉树,root为根结点编号,last是最后一个结点编号(注意引用),n为结点个数
bool isComplete(int root, int n) {
    queue<int> q;       // 定义队列
    q.push(root);       // 根结点入队
    int indexHeapNode = 1;
    while(n) {      // 只要n不为0,即还没有访问完全部非空结点
        int size = q.size();
        for(int i = 0; n && i < size; i++) {
            int front = q.front();      // 队首结点front
            q.pop();        // 弹出队首结点
            if(front == -1) return false;   // 访问到空结点,一定是非完全二叉树
            Heap[indexHeapNode++] = node[front].data;
            n--;    // 已访问的非空结点减少1
            q.push(node[front].left);       // 左孩子入队(包括空结点)
            q.push(node[front].right);      // 右孩子入队(包括空结点)
        }
        lastFull++;
    }
    return true;    // 已经访问完所有非空结点,还没有碰到空结点,一定是完全二叉树
}
// 对heap数组在[low, high]范围进行调整
// 其中low为欲调整结点的数组下标，high一般为堆的最后一个元素的数组下标
int downAdjust(int low, int high) {
    int numDownAdjust = 0;
    int i = low, j = i * 2;    // i为欲调整结点，j为其左孩子
    while(j <= high) {    // 存在孩子结点
        // 如果右孩子存在，且右孩子的值大于左孩子
        if(j + 1 <= high && Heap[j + 1] > Heap[j]) {
            j = j + 1;    // 让j存储右孩子下标
        }
        // 如果孩子中最大的权值比父亲大
        if(Heap[j] > Heap[i]) {
            swap(Heap[j], Heap[i]);    // 交换最大权值的孩子与父亲
            i = j;    // 令i为j、令j为i的左孩子，进入下一层
            j = i * 2;
            numDownAdjust++;
        } else {
            break;    // 孩子的权值均比父亲小，调整结束
        }
    }
    return numDownAdjust;
}
int makeHeap(int n) {    // 堆排序
    int numDownAdjust = 0;
    for(int i = n / 2; i >= 1; i--) {
        numDownAdjust += downAdjust(i, n);    // 建堆
    }
    return numDownAdjust;
}
int main() {
    int n;
    scanf("%d", &n);    // 输入结点个数
    for(int i = 1; i <= n; i++) {
        scanf("%d", &node[i].data);
    }
    memset(isRoot, true, sizeof(isRoot));       //初始化所有结点都是根结点
    for(int i = 1; i <= n; i++) {        // 对每一个结点
        int left = input(), right = input();    // 输入左右孩子编号
        if(left != -1) isRoot[left] = false;
        if(right != -1) isRoot[right] = false;
        isRoot[left] = isRoot[right] = false;   // 这两个编号一定不是根结点
        node[i].left = left;        // 记录左孩子
        node[i].right = right;      // 记录右孩子
    }
    int root = findRoot(n), height;       // 寻找根结点root,定义最后一个结点last
    if(!isAVL(root, height)) {
        printf("NOT AVL TREE!!!\n%d\n", numNotBalanced);
    } else if(!isComplete(root, n)) {
        printf("NOT COMPLETE TREE!!!\n%d\n", lastFull);
    } else {
        printf("OHHHHH HEAP!!!\n%d\n", makeHeap(n));
    }
    return 0;
}

Java :

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static class Node {

        int index;

        int weight;

        Node left;

        Node right;

        boolean balance() {
            final int leftD = left == null ? 0 : left.depth();
            final int rightD = right == null ? 0 : right.depth();
            return Math.abs(leftD - rightD) < 2;
        }

        int depth() {
            return Math.max(left == null ? 0 : left.depth(), right == null ? 0 : right.depth()) + 1;
        }

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int num = scanner.nextInt();
        final Node[] nodes = new Node[num];
        for (int i = 0; i < num; i++) {
            Node n = new Node();
            n.index = i;
            n.weight = scanner.nextInt();
            nodes[i] = n;
        }
        for (int i = 0; i < num; i++) {
            Node n = nodes[i];
            final String left = scanner.next();
            if (left.charAt(0) != '-') {
                n.left = nodes[Integer.parseInt(left) - 1];
            }

            final String right = scanner.next();
            if (right.charAt(0) != '-') {
                n.right = nodes[Integer.parseInt(right) - 1];
            }
        }
        final boolean[] root = new boolean[num];
        Arrays.fill(root, true);
        for (final Node node : nodes) {
            if (node.left != null) {
                root[node.left.index] = false;
            }
            if (node.right != null) {
                root[node.right.index] = false;
            }
        }

        Node rootNode = null;
        for (final Node node : nodes) {
            if (root[node.index]) {
                rootNode = node;
                break;
            }
        }

        int notB = notBalanceCount(rootNode);

        if (notB > 0) {
            System.out.println("NOT AVL TREE!!!");
            System.out.println(notB);
            return;
        }

        // complete check

        Stack<LinkedList<Node>> stack = new Stack<>();
        LinkedList<Node> q1;
        LinkedList<Node> q2 = new LinkedList<>();
        q2.offer(rootNode);
        int d = 0;
        boolean miss = false;
        while (!q2.isEmpty()) {
            d++;
            q1 = q2;
            q2 = new LinkedList<>();
            stack.push(q1);
            for (final Node n : q1) {
                if (n.left != null) {
                    if (miss) {
                        System.out.println("NOT COMPLETE TREE!!!");
                        System.out.println(d);
                        return;
                    } else {
                        q2.offer(n.left);
                    }
                } else {
                    miss = true;
                }
                if (n.right != null) {
                    if (miss) {
                        System.out.println("NOT COMPLETE TREE!!!");
                        System.out.println(d);
                        return;
                    } else {
                        q2.offer(n.right);
                    }
                } else {
                    miss = true;
                }
            }
        }

        //
        System.out.println("OHHHHH HEAP!!!");
        int count = 0;
        while (!stack.isEmpty()) {
            LinkedList<Node> q = stack.pop();
            while (!q.isEmpty()) {
                count += swap(q.pollLast());
            }
        }
        System.out.println(count);
    }


    static int swap(Node n) {
        if (n == null) {
            return 0;
        }
        int swapCount = 0;
        Node max = n;
        if (n.left != null && n.left.weight > max.weight) {
            max = n.left;
        }
        if (n.right != null && n.right.weight > max.weight) {
            max = n.right;
        }

        if (max != n && max.weight > n.weight) {
            int tmp = max.weight;
            max.weight = n.weight;
            n.weight = tmp;
            swapCount++;
            swapCount += swap(max);
        }
        return swapCount;
        //        int total = 0;
        //        if (n.left != null) {
        //            total += swap(n.left);
        //        }
        //        if (n.right != null) {
        //            total += swap(n.right);
        //        }
        //        Node ds = null;
        //        if (n.left != null && n.right != null) {
        //            if (n.left.weight > n.right.weight) {
        //                ds = n.left;
        //            } else {
        //                ds = n.right;
        //            }
        //        } else if (n.left != null && n.left.weight > n.weight) {
        //            ds = n.left;
        //        }
        //        if (ds != null && ds.weight > n.weight) {
        //            int tmp = ds.weight;
        //            ds.weight = n.weight;
        //            n.weight = tmp;
        //            total++;
        //        }
        //        return total;
    }

    static int notBalanceCount(Node n) {
        int total = 0;
        if (n.left != null) {
            total += notBalanceCount(n.left);
        }
        if (!n.balance()) {
            total++;
        }
        if (n.right != null) {
            total += notBalanceCount(n.right);
        }
        return total;
    }

}