摘要：中是數(shù)據(jù)堆的權(quán)重，也是數(shù)據(jù)堆排序的依據(jù)，是其在數(shù)據(jù)堆中的位置。改變數(shù)據(jù)的權(quán)重改變了數(shù)據(jù)節(jié)點(diǎn)的權(quán)重之后，需要重新進(jìn)行堆排序，將數(shù)據(jù)節(jié)點(diǎn)向上提升，或者將數(shù)據(jù)向下調(diào)整。

heap 堆是 swoole 實(shí)現(xiàn)定時(shí)器最重要的數(shù)據(jù)結(jié)構(gòu)，定時(shí)器將各個(gè)定時(shí)任務(wù)按照其下一次執(zhí)行的時(shí)間構(gòu)建最小堆，快速進(jìn)行插入與刪除。

heap 中 num 是現(xiàn)有數(shù)據(jù)堆的數(shù)量，size 是數(shù)據(jù)堆的大小，type 用于確定數(shù)據(jù)堆是最大堆還是最小堆，nodes 是數(shù)據(jù)堆的節(jié)點(diǎn)。swHeap_node 中 priority 是數(shù)據(jù)堆的權(quán)重，也是數(shù)據(jù)堆排序的依據(jù)，position 是其在數(shù)據(jù)堆中的位置。

typedef struct swHeap_node
{
    uint64_t priority;
    uint32_t position;
    void *data;
} swHeap_node;

typedef struct _swHeap
{
    uint32_t num;
    uint32_t size;
    uint8_t type;
    swHeap_node **nodes;
} swHeap;

創(chuàng)建一個(gè)數(shù)據(jù)堆就是初始化 swHeap 的各個(gè)屬性。

swHeap *swHeap_new(size_t n, uint8_t type)
{
    swHeap *heap = sw_malloc(sizeof(swHeap));
    if (!heap)
    {
        return NULL;
    }
    if (!(heap->nodes = sw_malloc((n + 1) * sizeof(void *))))
    {
        sw_free(heap);
        return NULL;
    }
    heap->num = 1;
    heap->size = (n + 1);
    heap->type = type;
    return heap;
}

數(shù)據(jù)入堆首先要檢查 heap 的 size 是否已經(jīng)足夠，如果不夠那么需要擴(kuò)容。

swHeap_bubble_up 函數(shù)負(fù)責(zé)將數(shù)據(jù)節(jié)點(diǎn)提升到數(shù)據(jù)堆中相應(yīng)的位置。方法很簡(jiǎn)單，新的數(shù)據(jù)節(jié)點(diǎn)不斷的和父節(jié)點(diǎn)進(jìn)行對(duì)比，符合條件就進(jìn)行替換，不符合條件就停止，結(jié)束。

swHeap_node* swHeap_push(swHeap *heap, uint64_t priority, void *data)
{
    void *tmp;
    uint32_t i;
    uint32_t newsize;

    if (heap->num >= heap->size)
    {
        newsize = heap->size * 2;
        if (!(tmp = sw_realloc(heap->nodes, sizeof(void *) * newsize)))
        {
            return NULL;
        }
        heap->nodes = tmp;
        heap->size = newsize;
    }

    swHeap_node *node = sw_malloc(sizeof(swHeap_node));
    if (!node)
    {
        return NULL;
    }
    node->priority = priority;
    node->data = data;
    i = heap->num++;
    heap->nodes[i] = node;
    swHeap_bubble_up(heap, i);
    return node;
}

#define left(i)   ((i) << 1)
#define right(i)  (((i) << 1) + 1)
#define parent(i) ((i) >> 1)

static void swHeap_bubble_up(swHeap *heap, uint32_t i)
{
    swHeap_node *moving_node = heap->nodes[i];
    uint32_t parent_i;

    for (parent_i = parent(i);
            (i > 1) && swHeap_compare(heap->type, heap->nodes[parent_i]->priority, moving_node->priority);
            i = parent_i, parent_i = parent(i))
    {
        heap->nodes[i] = heap->nodes[parent_i];
        heap->nodes[i]->position = i;
    }

    heap->nodes[i] = moving_node;
    moving_node->position = i;
}

static sw_inline int swHeap_compare(uint8_t type, uint64_t a, uint64_t b)
{
    if (type == SW_MIN_HEAP)
    {
        return a > b;
    }
    else
    {
        return a < b;
    }
}

改變了數(shù)據(jù)節(jié)點(diǎn)的權(quán)重之后，需要重新進(jìn)行堆排序，將數(shù)據(jù)節(jié)點(diǎn)向上提升，或者將數(shù)據(jù)向下調(diào)整。向下調(diào)整方法也很簡(jiǎn)單，不斷的和兩個(gè)子節(jié)點(diǎn)進(jìn)行比較，調(diào)整該數(shù)據(jù)節(jié)點(diǎn)和子節(jié)點(diǎn)的順序。

void swHeap_change_priority(swHeap *heap, uint64_t new_priority, void* ptr)
{
    swHeap_node *node = ptr;
    uint32_t pos = node->position;
    uint64_t old_pri = node->priority;

    node->priority = new_priority;
    if (swHeap_compare(heap->type, old_pri, new_priority))
    {
        swHeap_bubble_up(heap, pos);
    }
    else
    {
        swHeap_percolate_down(heap, pos);
    }
}

static void swHeap_percolate_down(swHeap *heap, uint32_t i)
{
    uint32_t child_i;
    swHeap_node *moving_node = heap->nodes[i];

    while ((child_i = swHeap_maxchild(heap, i))
            && swHeap_compare(heap->type, moving_node->priority, heap->nodes[child_i]->priority))
    {
        heap->nodes[i] = heap->nodes[child_i];
        heap->nodes[i]->position = i;
        i = child_i;
    }

    heap->nodes[i] = moving_node;
    moving_node->position = i;
}

static uint32_t swHeap_maxchild(swHeap *heap, uint32_t i)
{
    uint32_t child_i = left(i);
    if (child_i >= heap->num)
    {
        return 0;
    }
    swHeap_node * child_node = heap->nodes[child_i];
    if ((child_i + 1) < heap->num && swHeap_compare(heap->type, child_node->priority, heap->nodes[child_i + 1]->priority))
    {
        child_i++;
    }
    return child_i;
}

彈出堆頂元素后，需要重新調(diào)整整個(gè)數(shù)據(jù)堆。方法是將尾部元素和堆頂元素進(jìn)行交換，然后再對(duì)堆頂元素進(jìn)行排序。

void *swHeap_pop(swHeap *heap)
{
    swHeap_node *head;
    if (!heap || heap->num == 1)
    {
        return NULL;
    }

    head = heap->nodes[1];
    heap->nodes[1] = heap->nodes[--heap->num];
    swHeap_percolate_down(heap, 1);

    void *data = head->data;
    sw_free(head);
    return data;
}

刪除堆節(jié)點(diǎn)元素和彈出堆頂元素類(lèi)似，都是先將該元素和尾部元素進(jìn)行替換，然后再對(duì)其進(jìn)行排序。由于尾部元素不一定比待刪除的元素權(quán)重高，因此需要先判斷其權(quán)重，再?zèng)Q定是提升還是降低。

int swHeap_remove(swHeap *heap, swHeap_node *node)
{
    uint32_t pos = node->position;
    heap->nodes[pos] = heap->nodes[--heap->num];

    if (swHeap_compare(heap->type, node->priority, heap->nodes[pos]->priority))
    {
        swHeap_bubble_up(heap, pos);
    }
    else
    {
        swHeap_percolate_down(heap, pos);
    }
    return SW_OK;
}