【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆
根据UP的视频使用C++实现堆，不知道是否是不是最优，反正结果没问题😁
//上浮，从最后一个位置开始调整堆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);
}
=============优先队列=================
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(){
//优先队列
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;
}
