数据结构-堆（heap）

迷南。 2022-07-24 06:15 212阅读 0赞

堆（heap）也被称为优先队列（priority queue）。队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。而堆也是一样，在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。这个优先顺序可以是元素的大小或者其他规则。如图一所示就是一个堆，堆优先顺序就是大的元素排在前面，小的元素排在后面，这样得到的堆称为**最大堆**。最大堆中堆顶的元素是整个堆中最大的，并且每一个分支也可以看成一个最大堆。同样的，我们可以定义最小堆，如图二所示。

![这里写图片描述][1350354702_4619.jpg]  
来源：[http://blog.qiji.tech/archives/4855][http_blog.qiji.tech_archives_4855]

### 堆的存储 ###

堆可以看成一个二叉树，所以可以考虑使用二叉树的表示方法来表示堆。但是因为堆中元素按照一定的优先顺序排列，因此可以使用更简单的方法——**数组**——来表示，这样可以节省子节点指针空间，并且可以快速访问每个节点。堆得数组表示其实就是堆层级遍历的结果，如下图所示：

![这里写图片描述][heap.jpeg]  
来源：[http://rock3.info/blog/category/algorithm-and-data-structures/][http_rock3.info_blog_category_algorithm-and-data-structures]

这样对于每一个下标为i的节点，其左子节点在下标为2\*i的位置，其右子节点在下标为2\*i+1的位置，而其父节点在下标为 floor\{i / 2\}，其中i从1开始。通过数组的存储方式，可以通过计算下标，直接获取到相关节点。

typedef struct heap
    {
        int capacity;
        int size;
        int *arr;
    } Heap;
    
    #define MIN -1
    
    Heap* CreateEmptyHeap (int max) {
    
        Heap *heap = (Heap*)malloc(sizeof(Heap));
    
        if (heap == NULL) {
            printf("out of space!\n");
            return NULL;
        } 
    
        heap->capacity = max;
        heap->size = 0;
        heap->arr = (int*)malloc(sizeof(int) * (heap->capacity + 1));
        heap->arr[0] = MIN;
    
        return heap;
    }

以**最小堆**为例，说明堆得插入、删除等操作。

### 插入 ###

堆还可以看成一个完全二叉树，每次总是先填满上一层，再在下一层从左往右依次插入。堆的插入步骤：

1.  将新元素增加到堆的末尾
2.  按照优先顺序，将新元素与其父节点比较，如果新元素小于父节点则将两者交换位置。
3.  不断进行第2步操作，直到不需要交换新元素和父节点，或者达到堆顶
4.  最后通过得到一个最小堆

通过将新元素与父节点调整交换的操作叫做**上滤(percolate up)**。

![这里写图片描述][20151219140916955]  
来源：[http://blog.csdn.net/tuke\_tuke/article/details/50357939][http_blog.csdn.net_tuke_tuke_article_details_50357939]

Heap* Insert (Heap* heap, int val) {
    
        if (IsFull(heap)) {
            printf("heap is full!\n");
            return heap;
        }
    
        // percolate up new element
        int i;
        for (i = ++heap->size; heap->arr[i] > val; i /= 2) 
            heap->arr[i] = heap->arr[i/2];
        heap->arr[i] = val;
    
        return heap;
    }
    
    
    bool IsFull (Heap* heap) {
    
        return (heap->capacity == heap->size);
    }

### 删除 ###

堆的删除操作与插入操作相反，插入操作从下往上调整堆，而删除操作则从上往下调整堆。

1.  删除堆顶元素（通常是将堆顶元素放置在数组的末尾）
2.  比较左右子节点，将小的元素上调。
3.  不断进行步骤2，直到不需要调整或者调整到堆底。

上述调整的方法称为**下滤（percolate down）**。  
![这里写图片描述][20151219141009142]  
来源：[http://blog.csdn.net/tuke\_tuke/article/details/50357939][http_blog.csdn.net_tuke_tuke_article_details_50357939]

bool IsEmpty (Heap* heap) {
    
        return (heap->size == 0);
    }
    
    
    Heap* DeleteMin (Heap* heap) {
    
        if (IsEmpty(heap)) {
            printf("empty heap!\n");
            return NULL;
        }
    
        int minElement = heap->arr[1];
        int lastElement = heap->arr[heap->size--];
    
        int i, childIndex;
        for (i = 1; 2*i <= heap->size; i = childIndex)
        {
            childIndex = 2*i;
    
            //get the bigger child node
            if (heap->arr[childIndex] != heap->size 
             && heap->arr[childIndex] > heap->arr[childIndex+1])
                childIndex++;
    
            if (lastElement > heap->arr[childIndex])
                heap->arr[i] = heap->arr[childIndex];
            else
                break;
        }
        heap->arr[i] = lastElement;
    
        return heap;
    }

[1350354702_4619.jpg]: https://img-my.csdn.net/uploads/201210/16/1350354702_4619.jpg
[http_blog.qiji.tech_archives_4855]: http://blog.qiji.tech/archives/4855
[heap.jpeg]: http://rock3.info/wp-content/uploads/2013/12/heap.jpeg
[http_rock3.info_blog_category_algorithm-and-data-structures]: http://rock3.info/blog/category/algorithm-and-data-structures/
[20151219140916955]: /images/20220722/d77d5efff95f4e9185a629f083bcab80.png
[http_blog.csdn.net_tuke_tuke_article_details_50357939]: http://blog.csdn.net/tuke_tuke/article/details/50357939
[20151219141009142]: /images/20220722/2fc71f05feed4a5189de032d77d0ba26.png