ITPub博客

首页 > 数据库 > PostgreSQL > 数据库实现原理#5(FSM:最大堆二叉树)

数据库实现原理#5(FSM:最大堆二叉树)

原创 PostgreSQL 作者:husthxd 时间:2020-04-16 22:12:50 0 删除 编辑

PostgreSQL的FSM文件,其数据结构基础是最大堆二叉树,构建/删除/插入的相关代码详见代码注释.


#include "heap.h"
static int heap[MAX_ELEMENTS];
static int counter = 0;
//交换数据
static void swap(int *i,int *j)
{ 
  int tmp = *j;
  *j = *i;
  *i = tmp;
}
//打印堆信息
//n : 元素个数
void print_max_heap()
{
  for(int i = 1;i <= counter;i++)
  {
     printf("item[%d] is %d\n",i,heap[i]);
  }
}
//初始化堆数组
void init_heap(int *array,int n)
{
  for(int i=0;i < n;i++)
  {
    heap[i] = array[i];
  }
  counter = n;
}
//插入到最大堆
//item : 插入的值
//*n : 堆元素个数
void insert_max_heap(int item)
{
    if(HEAP_FULL(counter)){
      return;
    }
    //整个算法思想是首先把插入的值放在堆中的最后一个位置,然后为其找到合适的位置(递归向上)
    int i = ++counter;
    //i ≠ 1是因为数组的第一个元素并没有保存堆结点
    for(;(i != 1) && (item > heap[i/2]);i = i / 2){
      //如果插入的值比其父节点要大,把父节点的值交互到当前节点
      heap[i] = heap[i/2];//这里其实和递归操作类似,就是去找父结点
    }
    //父节点的值比当前值要大或者已到达根节点,设置当前位置的值为要插入的值
    heap[i] = item;
}
//删除最大堆中的元素
//*n : 堆元素个数
void delete_max_heap()
{
  //删除最大堆,总是删除最大堆的根节点
  if(HEAP_EMPTY(counter))
  {
     return;
  }
  //算法思想 : 把最后一个元素作为根节点,然后寻找该节点在树中合适的位置
  int lastone = heap[--counter];
  //父节点,初始化为1
  int parent = 1;
  for (int son=parent*2;son <= counter;son=son*2)
  {
    //删除父节点后,比较左右子节点的大小
    if(son < counter && heap[son] < heap[son+1])
    {
      //如果右子节点大于左子节点,切换到右子节点
      son++;
    }
    if (lastone > heap[son])
    {
      break;//已经比儿子要大,退出
    }
    //把子节点移到父节点
    //parent的位置就是lastone移动到的位置
    heap[parent]=heap[son];
    //递归,到下一层子树
    parent = son;
  }
  //parent的位置就是最后一个元素所在的位置
  heap[parent]=lastone;//lastone的实际位置已找到,赋值
}
//构建最大堆
//n : 元素个数
//heap是初始化但未构建的数组
void build_max_heap()
{
  for(int i = counter;i > 1;i--)
  {
    //从最后一个元素(最下层)开始遍历数组
    if(heap[i] > heap[i/2])
    {
      //子节点比父节点要大,交换父子节点
      swap(&(heap[i/2]),&(heap[i]));
      for(int j=i*2;j < counter;j=j*2)
      {
        //递归处理子节点
        if (j > counter)
        {
          break;
        }
        if(j < counter && heap[j+1] > heap[j])
        {
          //切换至右子节点
          j++;
        }
        if (heap[j] > heap[j/2])
        {
          //如果子节点大于父节点,交换
          swap(&(heap[j/2]),&(heap[j]));
        }
      }//end for#2
    }//end if
  }//end for#1
}
void build_max_heap_new()
{
  for(int i = counter/2;i > 1;i--)
  {
    //从子节点上一层开始处理
    //父节点为i
    int parent=i;
    //该节点的值
    int temp=heap[parent];
    for(int child=parent*2;child <=counter;child=child*2)
    {
      //
      if(child < counter && heap[child] < heap[child+1])
      {
        //切换到右子节点
        child++;
      }
      if(temp > heap[child])
        //父节点比子节点大,退出该父节点构成的树循环
        break;
      else
      {
        //把子节点的值放到父节点中
        heap[parent] = heap[child];
      }
      //进入到子节点,递归处理
      parent = child;
    }
    //已找到该父节点合适的位置,赋值
    heap[parent]=temp;
  }//end for#1
}

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/6906/viewspace-2686644/,如需转载,请注明出处,否则将追究法律责任。

全部评论
ITPUB数据库版块资深版主,对Oracle、PostgreSQL有深入研究。

注册时间:2007-12-28

  • 博文量
    1501
  • 访问量
    3964000