自建堆排序：

2023-04-05 11:53:15 来源：博客园

(资料图片)

建堆（heapification）：

蛮力算法

空堆反复调用insert()接口，消耗时间过多，第k轮迭代需O(logK)时间，正比于其深度：总共需要O(log n!) = O(n log n)；同理于自顶向下、自左向右的上滤操作；

实现时先入一个最大值元素，放在下标为0的地方，此后，元素从下标为1 的地方进行建堆，假设父节点下标是 i，则左右子节点是2*i，2*i+1；

class Priority_ueue{private:    int heap_size;    vectorheap;public:    Priority_ueue(){        heap.push_back(INT_MAX);        heap_size = 0;    }    void insert(int num){        heap.push_back(num);        ++heap_size;        int tmp = heap_size;        for(;num > heap[tmp/2];tmp /= 2){            heap[tmp] = heap[tmp/2];        }        heap[tmp] = num;    }//上滤    int delmax(){        if(heap_size == 0){            cout << "delmax error!" << endl;            return INT_MAX;        }else{            int res = heap[1];            int num = heap[heap_size--];            heap.pop_back();            int pos = 1, tmp = pos*2;            while(tmp < heap_size){                if(tmp+1 <= heap_size) tmp = heap[tmp] > heap[tmp+1] ? tmp : tmp + 1;                if(num < heap[tmp]){                    heap[pos] = heap[tmp];                    pos = tmp;                    tmp *= 2;                }else{                    break;                }            }//下滤            heap[pos] = num;            return res;        }    }    bool empty(){        return heap_size == 0;    }    int size(){        return heap_size;    }};

测试样例：

int main(){    int tmp;    Priority_queue q;    while(cin >> tmp){        q.insert(tmp);    }    while(!q.empty()){        cout << q.delmax() << endl;    }    return 0;}

floyd算法：

自下而上的、下滤操作：对所有的节点进行一次下滤，每个节点下滤所需的时间正比于其高度，故总体运行时间取决于高度总和；相较于蛮力算法，深度小的节点远远少于高度小的节点；

关键词：