数据结构--堆

堆类似于一颗完全二叉树，其中的每个节点都对应一个数值，它可用于堆排序，也可以作为数据结构成为优先级队列(Dijkstra算法就可以使用堆来进行描述),通常有两种性质的堆:

1.大顶堆:每个根节点的数值大于其孩子节点的数值

2.小顶堆:每个根结点的数值小于其孩子节点的数值

而常见的操作有:

1.heap_min(小顶堆，获取堆的最小元素),heap_max(大顶堆，获取堆的最大元素)

2.heap_length:获取堆的元素个数

3.heap_key:将堆中某个节点数值进行修改

4.heap_insert:向堆中插入某个节点

5.heap_extract:删除(大顶堆的)最大元素或(小顶堆的)最小元素.

下面开始进行部分程序分析：

这里采用的不是数组方式的堆结构，而采用了链表方式的堆结构，其中数据结构声明如下：

//堆中的节点
struct heap_node
{
    long value;
    struct heap_node *left;//左孩子节点
    struct heap_node *right;//右孩子节点
    struct heap_node *parent;//父节点
}
//堆中的根节点
struct heap_root
{
    struct heap_node *root;//根结点
    unsigned int length;//元素个数
    int flag:1;//堆的性质，大顶堆(1)，小顶堆(0)
}

堆中节点初始化

#define heap_node_init(ptr,_value)  ({\
        (ptr)->left = NULL;\
        (ptr)->right = NULL;\
        (ptr)->parent = NULL;\
        (ptr)->value = _value;})

堆中根节点初始化

#define heap_root_init(ptr,_flag,_value)  ({\
        heap_node_init(&ptr->root,_value);\
        ptr->length = 1;\
        ptr->flag = _flag;\
        })
#define heap_root_init_max(root) ({\
        heap_root_init(root,1);\
        })
#define heap_root_init_min(root) ({\
        heap_root_init(root,0);\
        })

由于根节点中存放的就是最大或最小元素，这样访问起来就方便多了

static inline struct heap_node* heap_min(struct heap_root *root)
{
        if(!root->flag)
           return &root->root;
           return NULL;
}

static inline struct heap_node*  heap_max(struct heap_root *root)
{
        if(root->flag)
            return &root->root;
            return NULL;
}

获取堆元素长度

static inline int heap_length(struct heap_root *root)
{
return root->length;
}

查找第一个没有左孩子或右孩子的节点

void _find_heap_node(struct heap_node **q,struct heap_root *root)
{
    int i,j;
    struct heap_node *p = &root->root;
    struct heap_node node[root->length];

    j=0;
    i=0;

    node[i  ].left = p;

    while(j<i)
    {
      p = node[j  ].left;

      if(!p->left||!p->right)
      {
        *q = p;
        return;
      }

      node[i  ].left = p->left;
      node[i  ].left = p->right;

    }
}

从父节点维护堆属性

static void _adjust_parent(struct heap_root* root,struct heap_node *node)
{
    struct heap_node *p = node;
    struct heap_node *q = p->parent;

    while(p&&q)
    {
    //max heap
    if(root->flag&&q->value >= p->value) break;

    else    //min heap
        if(!root->flag&&q->value <= p->value) break;
    else   //adjust
    {

        exchange(p,q);
        p = q;
        q = q->parent;
         }
    }

}

从子节点维护堆属性

static void _adjust_child(struct heap_root *root,struct heap_node *node)
{
    struct heap_node *left = node->left;
    struct heap_node *right = node->right;
    struct heap_node *temp = node;

    //max heap property
    if(root->flag) {

    if(left && left->value > temp->value) temp = left;
    if(right && right->value > temp->value) temp = right;

    if(temp != node)
    {
     exchange(temp,node);
    _adjust_child(root,temp);
    }

    }
    //min heap property
    else
    {
     if(left && left->value < temp->value ) temp = left;
     if(right && right->value < temp->value) temp = right;

     if(temp != node)
     {
        exchange(temp,node);
        _adjust_child(root,temp);
     }
    }
}

替换堆中的元素

int heap_key(struct heap_root *root,struct heap_node *node,long key)
{
    if(root->flag&&key<node->value) return -1;

    if(!root->flag&&key>node->value) return -1;

    node->value = key;
    _adjust_parent(root,node);

    return 0;
}

向堆中插入元素

int heap_insert(struct heap_root *root,struct heap_node *node)
{
    struct heap_node *p;

    //find the fisrt node which is empty on left node or right
    _find_heap_node(&p,root);


    if(p->left&&p->right) {
        return -1;
    }

    if(!p->left)
        p->left = node;
    else  if(!p->right)
        p->right = node;

    node->parent = p;
    root->length  =1;
    //无孩子节点，只能从父节点中维护堆属性
    _adjust_parent(root,node);

    return 0;
}

提取出最大或最小元素并维护堆的属性

struct heap_node* heap_extract(struct heap_root* root)
{
    struct heap_node *p,*q;

    p = NULL;
    q = NULL;

    if(root->length == 1)
    {
       root->length = 0;
       return &root->root;
    }

    _last_heap_node(&p,root);

    exchange(p,&root->root);

    q = p->parent;

    if(q->left == p)
        q->left = NULL;
    else
        q->right = NULL;

    root->length -= 1;
    //根节点，只能从孩子中维护其属性
    _adjust_child(root,&root->root);
    return p;

} heap.rar