大根堆小根堆

本文主要是介绍大根堆小根堆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

偷学的罒ω罒，非常好用的模版，分享一下。学过堆排应该很容易就看懂了，看不懂学一下堆排，不好懂的地方我也写了注释

小根堆

template<typename T>
class smallest_heap {
private://建堆T heap[10001];int len;
public:smallest_heap();void push(T const&);void pop();T top();int size();bool empty();
};
template<typename T>
smallest_heap<T>::smallest_heap() {len = 0;memset(heap, 0, sizeof(heap));
}
template<typename T>
void smallest_heap<T>::push(T const& n) {//将元素添加到堆尾heap[++len] = n;int son = len, father = son / 2;//由于是建立小根堆，当子节点小于父节点时，且父节点要大于等于最小下标while (heap[son] < heap[father] && father >= 1) {//交换std::swap(heap[son], heap[father]);//不断往上交换son = father, father = son / 2;}
}
//删除堆顶元素
template<typename T>
void smallest_heap<T>::pop() {//交换首元素和尾元素std::swap(heap[1], heap[len]);//将最后一个元素置0heap[len--] = 0;int father = 1, son = 2;//当子元素下标不超过最后一个while (son <= len) {//这一行用于找到当前节点的左右孩子中值较小的那一个，将其索引赋给 son。if (son<len && heap[son]>heap[son + 1])son++;//有序堆，只需要找到一个heap[son]>heap[father]的节点，否则就往上交换if (heap[father] > heap[son]) {std::swap(heap[father], heap[son]);father = son, son = father * 2;}else break;}
}
template<typename T>
T smallest_heap<T>::top() {return heap[1];
}
template<typename item>
int smallest_heap<item>::size() {return len;
}template<typename item>
bool smallest_heap<item>::empty() {return len;
}

很容易找到堆里的最小元素。

大根堆，改三个大于小于号就好了

template<typename T>
class smallest_heap {
private://建堆T heap[10001];int len;
public:smallest_heap();void push(T const&);void pop();T top();int size();bool empty();
};
template<typename T>
smallest_heap<T>::smallest_heap() {len = 0;memset(heap, 0, sizeof(heap));
}
template<typename T>
void smallest_heap<T>::push(T const& n) {heap[++len] = n;int son = len, father = son / 2;//1.大根堆改这里<改成>while (heap[son] > heap[father] && father >= 1) {//交换std::swap(heap[son], heap[father]);//不断往上交换son = father, father = son / 2;}
}
//删除堆顶元素
template<typename T>
void smallest_heap<T>::pop() {//交换首元素和尾元素std::swap(heap[1], heap[len]);//将最后一个元素置0heap[len--] = 0;int father = 1, son = 2;//当子元素下标不超过最后一个while (son <= len) {//大根堆改这，>改成<if (son<len && heap[son]<heap[son + 1])son++;//这里同理if (heap[father] < heap[son]) {std::swap(heap[father], heap[son]);father = son, son = father * 2;}else break;}
}
template<typename T>
T smallest_heap<T>::top() {return heap[1];
}
template<typename item>
int smallest_heap<item>::size() {return len;
}template<typename item>
bool smallest_heap<item>::empty() {return len;
}

这篇关于大根堆小根堆的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---