堆

约 208 个字 59 行代码预计阅读时间 1 分钟

1. 基础知识

一个size为\(n\)的heap, 上一层对应的根节点值是\(\lfloor \frac{n}{2} \rfloor\)

2. 基本代码

struct heapstruct{
    int size;
    int* nodes;
};
typedef struct heapstruct *PtrToHeap;

void Insert(int x, PtrToHeap h){
    h->size++;
    h->nodes[h->size]=x;
    PercolateUp(h->size,h);
}

void PercolateUp(int p, PtrToHeap h){
    int insert = h->nodes[p];
    int i;
    for(i=p;i/2>=1&&h->nodes[i/2]>insert;i/=2){
        h->nodes[i]=h->nodes[i/2];
    }
    h->nodes[i]=insert;
}

//DeleteMin, 一定是删掉根节点

int DeleteMin(PtrToHeap h){
    //把最后一个节点移到根节点
    int element = h->nodes[1];
    h->nodes[1]=h->nodes[h->size];
    h->size--;
    //下滤
    PercolateDown(1,h);
    return element;
}

void PercolateDown(int x, PtrToHeap h){
    int element = h->nodes[x];
    int p=x;
    int child=p*2;
    for(p=x;2*p<h->size+1;p=child){
        child=p*2;
        if(2*p+1<h->size+1){
            if(h->nodes[2*p+1]<h->nodes[2*p]){
                child=2*p+1;
            }
        }
        if(element>h->nodes[child]){
            h->nodes[p]=h->nodes[child];
        }
        else{
            break;
        }
    }
    h->nodes[p]=element;
}
void BuildHeap(PtrToHeap h){
    int i;
    for(i=h->size/2;i>=0;i--){
        PercolateDown(i,h);
    }
}

剩下的：

DecreaseKey: 先减去一个\(\Delta\)之后PercolateUp, Increase同理。
Delete(p)，把DeleteMin的1改成p就可以了。

3. 理论题

Important

Heap理论题中默认下标也是从 \(1\) 开始的。

对于节点\(i\)
父节点：\(\lfloor \dfrac{i + d - 2}{d} \rfloor\)
第一个孩子：\((i - 1)d + 2\)
最后一个孩子：\(id + 1\)

选择题里可以拿三叉堆算一下。

Which of the following statements about d-heaps is True?

A. In a complete d-heap, the number of leaf nodes is less than the number of internal nodes.
B. The height of a d-heap with n elements is directly proportional to n.
C. D-heaps are used for sorting data in ascending order.
D. In a d-heap, the parent of a given node can be found using integer division.

Answer

D√，C不准确，也可以用来降序。

堆

1. 基础知识

2. 基本代码

3. 理论题

Comments