堆是完全二叉树 在第五章的时候创建了一个二分搜索树 既然都是二叉树 那为什么堆不用二分搜索树的结构

Question

在堆中是用数组实现的
    MaxHeap(int capacity) {
        data = new Item[capacity + 1];
        count = 0;
        this->capacity = capacity;
    }

在二分搜索树是用一个结构体的结构实现的
    struct Node {
        Key key;
        Value value;
        Node *left;
        Node *right;
        
        Node(Key key, Value value) {
            this->key = key;
            this->value = value;
            this->left = this -> right = NULL;
        }
    };

那既然两个都是二叉树 为什么在实现堆的时候 不用二分搜索树的结构体里的结构 而是用数组呢?

Answer 1

liuyubobobo 2017-10-11 01:26:41

因为堆是一棵完全二叉树，可以方便的使用数组的形式表达，这样不仅节省了left,right两个指针的空间，还完全不需要麻烦的指针操作。实现堆使用数组做底层结构，不尽代码简洁，总体效率也高。当然了，如果你愿意，也完全可以使用二叉树结构体的方式来实现堆：）