以下内容是关于动态实现的,如下所示

(1)给定一组数据(随便),构造最小堆;
(2)利用同一组数据为输入序列,实现优先权队列。
如何将这个问题动态实现?

阿晨1998
浏览 209回答 2
2回答

慕勒3428872

/**根据你需要java的要求, 写了一个实现。这个是一个整数最小优先的堆,只实现了加入功能。应该还有删除,清空等功能,但并不是必须的。你可以自己尝试实现。测试为生成一组随机数,加入队列,每次加入后都察看一下堆的最优先元素是多少。如果还有疑问 ,至邮件:tazerkinq@163.com*/public class Heap {int[] heap; //堆的储存空间int size; //当前的元素的数量Heap() {size = 0; //初始化数量为0heap = new int[1024]; //预留空间1024,为了操作方便,0位置被弃用}void add(int e){ //加入新的元素,也是维护堆的主要地方之一int i = ++size; //数量增加一, 并用临时变量记录此位置while(( 1<i ) && ( e<heap[i/2] )){ //判断e是否小于父节点的元素, 如否,则停止heap[i] = heap[i/2]; //如是, 则移动父节点元素当i记录位置i/=2; //i继续向上迭代,指向刚才父节点的位置}heap[i] = e; //该位置即为元素最终位置}int peek(){ //返回堆头的元素return heap[1]; //数组下标1的元素即是} //当然如果当前元素为空的话,返回的则是初始值int size(){ //返回当前元素数目return size;}public static void main(String[] args) {Heap h = new Heap();for(int i=0;i<100;i++){int k=(int)(10000*Math.random()); //随机生成一个整数h.add(k); //加入到堆中System.out.printf("Currently adding number is %5d.\t"+"Currently priority number is %5d.%n",k,h.peek()); //输出生成的随机数,并且输出该堆的优先元素}}}

沧海一幻觉

最小堆的优先队列实现。在建立最小堆或最大堆时。最主要的就是理解。SiftDown和SiftUp算法的实现问题。其实我觉得自己在画一棵树。先比较左右再比较父点之间。是最大堆往上。最小堆往下。就很能理解了,下面程序是最小堆。#include <iostream>using namespace std;template<class Elem>class MinHeap{private:Elem* heapArray;int CurrentSize;int MaxSize;public:MinHeap(const int n);virtual~ MinHeap(){delete []heapArray;}void BuildHeap();bool isLeaf(int pos) const;int leftChild(int pos) const;int rightChild(int pos) const;//return parent positionint parent(int pos) const;//删除给定下标的元素。bool Remove(int pos,Elem& node);void SiftDown(int left);void SiftUp(int position);bool Insert(const Elem& newNode);Elem& RemoveMin();bool print() const;};template<class Elem>MinHeap<Elem>::MinHeap(const int n){if(n<=0)return ;CurrentSize=0;MaxSize=n;heapArray=new Elem[MaxSize];BuildHeap();}template<class Elem>void MinHeap<Elem>::BuildHeap(){for(int i=CurrentSize/2-1;i>=0;i--)SiftDown(i);}template<class Elem>bool MinHeap<Elem>::isLeaf(int pos) const{return (pos>=CurrentSize/2) && (pos<CurrentSize);}template<class Elem>int MinHeap<Elem>::leftChild(int pos) const{return 2*pos+1;}template<class Elem>int MinHeap<Elem>::rightChild(int pos) const{return 2*pos+2;}template<class Elem>int MinHeap<Elem>::parent(int pos) const{return (pos-1)/2;}//向下筛选。template<class Elem>void MinHeap<Elem>::SiftDown(int left){int i=left; 。 //标记父结点int j=2*i+1;Elem temp=heapArray[i];while(j<CurrentSize){if((j<CurrentSize-1) && (heapArray[j]>heapArray[i]))j++; //指向右子结点if(temp>heapArray[j]){heapArray[i]=heapArray[j];i=j;j=2*j+1;}elsebreak;}heapArray[i]=temp;}//向上筛选template<class Elem>void MinHeap<Elem>::SiftUp(int position){int temppos=position;Elem temp=heapArray[temppos];while((temppos>0) && (heapArray[parent(temppos)]>temp)){heapArray[temppos]=heapArray[parent(temppos)];temppos=parent(temppos);}heapArray[temppos]=temp;}template<class Elem>bool MinHeap<Elem>::Insert(const Elem& newNode){if(CurrentSize==MaxSize)return false;heapArray[CurrentSize]=newNode;SiftUp(CurrentSize);CurrentSize++;return true;}template<class Elem>Elem& MinHeap<Elem>::RemoveMin(){if(CurrentSize==0){cout<<"Can't Delete ";}else{Elem temp=heapArray[0];heapArray[0]=heapArray[CurrentSize-1];CurrentSize--;if(CurrentSize>1)SiftDown(0);return temp;}}template<class Elem>bool MinHeap<Elem>::Remove(int pos,Elem& node){if((pos<0) || (pos>CurrentSize))return false;Elem temp=heapArray[pos];heapArray[pos]=heapArray[--CurrentSize];SiftUp(pos);SiftDown(pos);node=temp;return true;}template<class Elem>bool MinHeap<Elem>::print() const{if(CurrentSize<0)return false;for(int i=0;i<CurrentSize;i++)cout<<heapArray[i]<<" ";return true;}int main(){MinHeap<char> A(20);char item;int pos;cout<<"Enter 20 number:"<<endl;for(int i=0;i<20;i++){cout<<"the"<<i<<"NO: ";cin>>item;A.Insert(item);}cout<<"\nPrint all the number: ";A.print();A.RemoveMin();cout<<"\nAfter delete the Min number:";A.print();cout<<"\nEnter the positon you want:";cin>>pos;A.Remove(pos,item);cout<<"\nThe data is:"<<item<<endl;return 0;}//程序示例:/*Enter 20 number:the0NO: athe1NO: qthe2NO: zthe3NO: wthe4NO: sthe5NO: xthe6NO: ethe7NO: dthe8NO: cthe9NO: rthe10NO: fthe11NO: vthe12NO: tthe13NO: gthe14NO: bthe15NO: ythe16NO: hthe17NO: nthe18NO: uthe19NO: jPrint all the number: a c b d f t e h n j r z v x g y w q u sAfter delete the Min number:c f b d r t e h n j s z v x g y w q uEnter the positon you want:13The data is:x*/给定一个数组,当中有正负数,求当中的一段“子数组”(即任意长度,连续的数字),使得这个“子数组”的和是所有“子数组”和中最大的,如给定的数组为12, -8, 5, 66, -21, 0 ,35, -44,7,则最大的和的子数组为{12, -8, 5, 66, -21, 0 ,35},最大的和为89.package arraytest;public class GetMaxArray {// 复杂度为o(n^2)public void findMax(int s[]) {int add[] = new int[100];int k = s[0];int b = 0;// 标记开始位置int p = 0;// 标记结束位置int i;int j;for (i = 0; i <= s.length; i++)// 整体循环{for (j = i; j < s.length; j++)// 子数组循环{add[i] += s[j];if (add[i] > k) {k = add[i];b = i;// 获得开始位置下标p = j;// 获得结束位置下标}}}System.out.print("max sub array:");System.out.print("{");for (i = b; i <= p; i++) {System.out.print(s[i] + " ");}System.out.println("}");System.out.println("sum:" + k);}// 复杂度为o(n)public int findMax(int a[], int size) {int i, max = 0, temp_sum = 0;for (i = 0; i < size; i++) {temp_sum += a[i];if (temp_sum > max)max = temp_sum;else if (temp_sum < 0)temp_sum = 0;}System.out.print("sum:" + max);return max;}public static void main(String[] args) {int s[] =// { 101, -100, 100, 100, 999, -222 - 100, 100 };{ 12, -8, 5, 66, -21, 0, 35, -44, 7 };GetMaxArray test = new GetMaxArray();test.findMax(s);test.findMax(s, s.length);}}
打开App,查看更多内容
随时随地看视频慕课网APP