使用 C 的 DSA - 堆

概述

堆表示一种特殊的基于树的数据结构，用于表示优先级队列或堆排序。我们将专门讨论二叉堆树。

二叉堆树可以归类为具有两个约束的二叉树 −

• 完整性 − 二叉堆树是一棵完整的二叉树，除了最后一级可能不包含所有元素，但从左到右的元素应该被填充。

• 堆性 − 所有父节点都应该大于或小于其子节点。如果父节点大于其子节点，则称为最大堆，否则称为最小堆。最大堆用于堆排序，最小堆用于优先级队列。我们正在考虑最小堆，并将使用数组实现。

基本操作

以下是最小堆的基本主要操作。

• 插入 − 在堆中插入一个元素。

• 获取最小值 − 从堆中获取最小元素。

• 删除最小值 − 从堆中删除最小元素

插入操作

• 每当要插入一个元素时。在数组末尾插入元素。将堆的大小增加 1。

• 当堆属性被破坏时，将元素堆积起来。将元素与父元素的值进行比较，并根据需要交换它们。

void insert(int value) {            
   size++;
   intArray[size - 1] = value;
   heapUp(size - 1);
}
void heapUp(int nodeIndex){
   int parentIndex, tmp;
   if (nodeIndex != 0) {
      parentIndex = getParentIndex(nodeIndex);
      if (intArray[parentIndex] > intArray[nodeIndex]) {
         tmp = intArray[parentIndex];
         intArray[parentIndex] = intArray[nodeIndex];
         intArray[nodeIndex] = tmp;
         heapUp(parentIndex);
      }
   }
}

获取最小值

获取实现堆的数组的第一个元素作为根。

int getMinimum(){
   return intArray[0];
}

删除最小值

• 每当要删除一个元素时。获取数组的最后一个元素并将堆大小减少 1。

• 当堆属性被破坏时，将元素向下堆。将元素与子元素的值进行比较，并在需要时交换它们。

void removeMin() {
   intArray[0] = intArray[size - 1];
   size--;
   if (size > 0)
      heapDown(0);
}
void heapDown(int nodeIndex){
   int leftChildIndex, rightChildIndex, minIndex, tmp;
   leftChildIndex = getLeftChildIndex(nodeIndex);
   rightChildIndex = getRightChildIndex(nodeIndex);
   if (rightChildIndex >= size) {
      if (leftChildIndex >= size)
         return;
      else
         minIndex = leftChildIndex;
   } else {
      if (intArray[leftChildIndex] <= intArray[rightChildIndex])
         minIndex = leftChildIndex;
      else
         minIndex = rightChildIndex;
   }
   if (intArray[nodeIndex] > intArray[minIndex]) {
      tmp = intArray[minIndex];
      intArray[minIndex] = intArray[nodeIndex];
      intArray[nodeIndex] = tmp;
      heapDown(minIndex);
   }
}

示例

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

int intArray[10];
int size;

bool isEmpty(){
   return size == 0;
}
int getMinimum(){
   return intArray[0];
}
int getLeftChildIndex(int nodeIndex){
   return 2*nodeIndex +1;
}
int getRightChildIndex(int nodeIndex){
   return 2*nodeIndex +2;
}
int getParentIndex(int nodeIndex){
   return (nodeIndex -1)/2;
}
bool isFull(){
   return size == 10;
}
/**
* 将新元素堆积起来，直到堆属性被破坏。
* 步骤：
* 1. 将节点的值与父节点的值进行比较。
* 2. 如果顺序错误，则交换它们。
* */
void heapUp(int nodeIndex){
   int parentIndex, tmp;
   if (nodeIndex != 0) {
      parentIndex = getParentIndex(nodeIndex);
      if (intArray[parentIndex] > intArray[nodeIndex]) {
         tmp = intArray[parentIndex];
         intArray[parentIndex] = intArray[nodeIndex];
         intArray[nodeIndex] = tmp;
         heapUp(parentIndex);
      }
   }
}
/**
* 将值最小的根元素向下堆，直到堆属性被破坏。
* 步骤：
* 1.如果当前节点没有子节点，则完成。
* 2.如果当前节点有一个子节点并且堆属性被破坏，
* 3.交换当前节点和子节点并向下堆。
* 4.如果当前节点有一个子节点并且堆属性被破坏，则找到较小的一个
* 5.交换当前节点和子节点并向下堆。
* */
void heapDown(int nodeIndex){
   int leftChildIndex, rightChildIndex, minIndex, tmp;
   leftChildIndex = getLeftChildIndex(nodeIndex);
   rightChildIndex = getRightChildIndex(nodeIndex);
   if (rightChildIndex >= size) {
      if (leftChildIndex >= size)
         return;
      else
         minIndex = leftChildIndex;
   } else {
      if (intArray[leftChildIndex] <= intArray[rightChildIndex])
         minIndex = leftChildIndex;
      else
         minIndex = rightChildIndex;
   }
   if (intArray[nodeIndex] > intArray[minIndex]) {
      tmp = intArray[minIndex];
      intArray[minIndex] = intArray[nodeIndex];
      intArray[nodeIndex] = tmp;
      heapDown(minIndex);
   }
}
void insert(int value) {            
   size++;
   intArray[size - 1] = value;
   heapUp(size - 1);
}
void removeMin() {
   intArray[0] = intArray[size - 1];
   size--;
   if (size > 0)
      heapDown(0);
}
main() {
   /*                     5                //Level 0
   * 
   */
   insert(5);
   /*                     1                //Level 0
   *                     |
   *                 5---|                 //Level 1
   */   
   insert(1);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   */
   insert(3);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   *                 |
   *              8--|                     //Level 2
   */
   insert(8);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   *                 |
   *              8--|--9                  //Level 2
   */
   insert(9);
   /*                     1                 //Level 0
   *                     |
   *                 5---|---3              //Level 1
   *                 |       |
   *              8--|--9 6--|              //Level 2
   */
   insert(6);
   /*                     1                 //Level 0
   *                     |
   *                 5---|---2              //Level 1
   *                 |       | 
   *              8--|--9 6--|--3           //Level 2
   */
   insert(2);

   printf("%d", getMinimum());

   removeMin();
   /*                     2                 //Level 0
   *                     |
   *                 5---|---3              //Level 1
   *                 |       |
   *              8--|--9 6--|              //Level 2
   */
   printf("
%d", getMinimum());   
}

如果我们编译并运行上述程序，则会产生以下结果 −

1
2