最大堆和最小堆

标签（空格分隔）： 数据结构与算法

---

定义:

1. 它是一颗完全二叉树,它可以是空
2. 树中结点的值总是不大于或者不小于其孩子结点的值
3. 每一个结点的子树也是一个堆

当父结点的键值总是大于或等于任何一个子结点的键值时为:最大堆,当父结点的键值总是小于或等于任何一子节点的键值时:最小堆.

下面我们以最大堆来为例作为讲解
下图就是一个最大堆

image.png

构造最大堆

对于一个给定的数据 Arr = {5, 1, 13, 3, 16, 7, 10, 14, 6, 9},如何构造出一个最大堆呢?
首先它是一颗完全二叉树,因此我们可以使用顺序存储.对应的完全二叉树如下图:

image.png

开始构造最大堆:

1.首先我们需要找到最后一个结点的父结点如图(a),我们找到的结点是16,然后找出该结点的最大子节点与自己比较,若该子节点比自身大,则将两个结点交换.
图(a)中,16是最大的结点,不需要交换.
2.我们移动到第下一个父结点3,如图(b)所示.同理做第一步的操作,交换了3和14,结果如图(c)所示.
3.移动结点到下一个父结点13,如图(d)所示,发现不需要做任何操作,
4.移动到下个父结点1,如图(e)所示,然后交换1和16,如图(f)所示,此时我们发现交换后,1的子节点并不是最大的,我们接着在交换(如图g)所示
5.移动到父结点到5,一次重复上述步骤,交换5和16,在交换14和5,在交换5和6
所有节点交换完毕,最大堆构建完成

image.png

typedef int ElementType;
typedef struct HeapStruct *MaxHeap;
struct HeapStruct {
    //指向一个数组
    ElementType *Element;
    //堆当前元素的个数
    int size;
    //堆的最大容量
    int capacity;
};


int maxIndex(int left, int right, MaxHeap heap);

void initHeap(int *arr, int size, MaxHeap &heap, int maxCapacity) {

    heap = (MaxHeap)malloc(sizeof(HeapStruct));
    heap->capacity = maxCapacity;
    heap->Element = new ElementType[maxCapacity+1];
    heap->size = size;
    //第一个位置不存任何数据,交换结点时可以作为中间变量
    heap->Element[0] = 0;
    //构建完全二叉树
    for (int i = 0; i < size; i++) {
        heap->Element[i+1] = arr[i];
    }

    //寻找最后一个结点的父结点,作为初始值
    for (int pIndex = heap->size / 2; pIndex >= 1; pIndex--) {
        int tmp = pIndex;
        while ((tmp<<1) <= heap->size) { //表示该结点有孩子结点-->当该结点时叶子结点时,循环结束
            //寻找这个结点的最大子结点
            int maxChildIndex = 0;
            if ((tmp<<1) + 1 > heap->size) { //没有右孩子,则左孩子就是最大子结点
                maxChildIndex = (tmp<<1);
            } else {//从左右孩子中寻找最大子结点
                maxChildIndex = maxIndex(tmp<<1,  (tmp<<1) + 1, heap);
            }
            //比较最大子结点和当前父结点,如果父结点的值小于最大子结点的值,则交换两个结点
            if (heap->Element[tmp] < heap->Element[maxChildIndex]) {
                //交换两个结点
                heap->Element[0] = heap->Element[tmp];
                heap->Element[tmp] = heap->Element[maxChildIndex];
                heap->Element[maxChildIndex] = heap->Element[0];
                heap->Element[0] = 0;
                tmp = maxChildIndex;
            } else {
                break;//当该结点不需要在交换时,结束向下查找
            }
        }
    }
}

int maxIndex(int left, int right, MaxHeap heap) {
    return heap->Element[left] > heap->Element[right] ? left : right;
}

最大堆中插入一个结点

原理:现在堆的最后增加一个结点,然后沿这堆树上升.

int maxHeapInsert(ElementType e, MaxHeap heap) {
    //检查是否到达了堆的最大容量
    if (heap->capacity == heap->size) {
        return -1;
    }

    heap->size++;
    heap->Element[heap->size] = e;
    for (int sIndex = heap->size; sIndex > 1;) {
        //寻找这个结点的父结点
        int pIndex = sIndex / 2;
        if (heap->Element[pIndex] < heap->Element[sIndex]) {
            heap->Element[0] = heap->Element[pIndex];
            heap->Element[pIndex] = heap->Element[sIndex];
            heap->Element[sIndex] = heap->Element[0];
            heap->Element[0] = 0;
            sIndex = pIndex;
        } else {
            break;
        }
    }
}

最大堆中删除一个元素

原理:将堆的最后的结点提到根结点，然后删除最大值，然后再把新的根结点向下进行调整,直到找到其符合的的位置.

int maxHeapPopE(MaxHeap heap, ElementType *e) {
    if (heap->size == 0) {
        return -1;
    }
    *e = heap->Element[1];
    heap->Element[1] = heap->Element[heap->size];
    heap->size--;
    int pIndex = 1;
    while (pIndex <<1 <= heap->size) { //有子结点
        int maxChild = 0;
        if ((pIndex << 1) + 1 > heap->size) { //没有右孩子
            maxChild = pIndex << 1;
        } else {
            maxChild = maxIndex(pIndex << 1, (pIndex << 1) + 1, heap);
        }
        if (heap->Element[pIndex] < heap->Element[maxChild]) {
            heap->Element[0] = heap->Element[pIndex];
            heap->Element[pIndex] = heap->Element[maxChild];
            heap->Element[maxChild] = heap->Element[0];
            heap->Element[0] = 0;
            pIndex = maxChild;
        } else {
            break;
        }
    }
}

下面我们测试一下代码

int main() {
    int arr[] = { 5, 1, 13, 3, 16, 7, 10, 14, 6, 9 };
    
    MaxHeap heap = nullptr;
    initHeap(arr, sizeof(arr) / sizeof(int), heap,20);

     maxHeapInsert(18, heap);

     ElementType e;
     maxHeapPopE(heap, &e);

     cout << " e = " << e << endl;

    for (int i = 1; i <= heap->size; i++) {
        cout << heap->Element[i] << endl;
    }

    system("pause");
    return 0;
}