【從堆的定義到優(yōu)先隊列、堆排序】 10分鐘看懂必考的數(shù)據(jù)結(jié)構(gòu)——堆
根據(jù)UP的視頻使用C++實現(xiàn)堆，不知道是否是不是最優(yōu)，反正結(jié)果沒問題??
//上浮，從最后一個位置開始調(diào)整堆O(nlogn)
void shiftUp(vector<int> &as){
??size_t child = as.size() - 1;
??size_t parent = (child - 1)/ 2 ;
??while(parent < as.size()){
????/* if(child + 1 < as.size() && as[child] < as[child + 1]){ */
????/*???++child; */
????/* } */
????if(as[parent] < as[child]){
??????swap(as[parent] , as[child]);
??????child = parent;
??????parent = (child - 1)/ 2;
????}else{
??????break;
????}
??}
}
template <typename Container>
void print(const Container & con){
??for(auto &elem : con){
????cout << elem << " ";
??}
??cout << endl;
}
void test0(){
??vector<int> vec = {3,4,5,6,1,7,8};
??vector<int> as;
??for(const auto & elem : vec){
????as.emplace_back(elem);
????shiftUp(as);
??}
??print(vec);
??print(as);
}
下濾
template<typename Conpare = std::less<int>>
void heapify(vector<int> &heap,int i,size_t size){
??size_t parent = i;
??size_t child = parent * 2 + 1;
??while(child < heap.size()){
????if(child + 1 < heap.size() && Conpare()(heap[child],heap[child + 1])){
??????child++;
????}
????if(Conpare()(heap[parent],heap[child])){
??????swap(heap[parent] , heap[child]);
??????parent = child;
??????child = parent * 2 + 1;
????}else{
??????break;
????}
??}
}
==============分隔線=================
template<typename Conpare = std::less<int>>
?void heapify(vector<int> &heap,int i,size_t size){
???size_t parent = i;
???size_t child = parent * 2 + 1;
?
???while(child < heap.size()){
?????if(child + 1 < heap.size() && Conpare()(heap[child],heap[child + 1])){
???????child++;
?????}
?????if(Conpare()(heap[parent],heap[child])){
???????swap(heap[parent] , heap[child]);
?
???????parent = child;????????????????????????????
???????child = parent * 2 + 1;
?????}else{
???????break;
?????}
???}
?
?}
//下浮
void buildHeap(vector<int> &heap){
??size_t lastNotLeaf = heap.size()/2 - 1;
??for(int i = lastNotLeaf ; i >= 0 ; --i){
????heapify<std::greater<int>>(heap,i,heap.size());
??}
}
void test1(){
??vector<int> vec = {3,4,5,6,1,7,8};
??buildHeap(vec);
??print(vec);
}
=============優(yōu)先隊列=================
template<typename Conpare = std::less<int>>
void heapify(vector<int> &heap,int i,size_t size){
??size_t parent = i;
??size_t child = parent * 2 + 1;
??while(child < heap.size()){
????if(child + 1 < heap.size() && Conpare()(heap[child],heap[child + 1])){
??????child++;
????}
????if(Conpare()(heap[parent],heap[child])){
??????swap(heap[parent] , heap[child]);
??????parent = child;
??????child = parent * 2 + 1;
????}else{
??????break;
????}
??}
}
int pop(vector<int> &queue){
??int front = queue.front();
??queue[0] = queue.back();
??if(!queue.empty()) queue.pop_back();
??heapify<std::greater<int>>(queue,0,queue.size());
??return front;
}
void test2(){
??//優(yōu)先隊列
??vector<int> vec = {1,3,2,6,5,10,12};
??size_t size = vec.size();
??for(size_t i = 0 ; i < size ; ++i){
????int min = pop(vec);
????cout << min << " ";
??}
??cout << endl;
}
