精华内容
下载资源
问答
  • 有一个技巧点是数组的第一个元素可以作为“哨兵”,存放最小最小的一个数字(最小堆),它比堆中任意一个元素都要小,这样方便后序的插入、删除等操作。 我们知道,有两种建立堆的方式: 1.将一个个元
    • 题目
      05-树7 堆中的路径 (25分)
    • 分析
      这道题考察建立最小堆的基本操作。
      首先堆是一种优先队列,可以用完全二叉树的方式来表示,从根结点到任意结点路径上都是有序的。完全可以用数组来存储。
      有一个技巧点是数组的第一个元素可以作为“哨兵”,存放最小的一个数字(最小堆),它比堆中的任意一个元素都要小,这样方便后序的插入、删除等操作。
      我们知道,有两种建立堆的方式:
      1. 将一个个元素插入初始为空的堆中,这样每次插入的时间复杂度为O(logN),N个元素都插入之后建好堆,时间复杂度为O(N*logN)。
        //但是这道题只能这样做,因为题中明确说明:
        * 将一系列给定数字插入一个初始为空的小顶堆H[]*
      2. 将N个结点先顺序存入数组,使之符合完全二叉树的结构特性;然后依次从各个结点(从N/2 到 1位置上的结点)开始调整,使之子树成为最小堆。那么最后调整位置为1的结点后,整个树就是一个最小堆了。这样的时间复杂度为O(N)
    • 我的代码一(方法一,java语言描述)
    package pat;
    import java.util.Scanner;
    public class CreateHeap {
        static int capicity = 1001;
        static int minNum = -10001;
        static int[] minHeap = new int[capicity];
        static{
            minHeap[0] = minNum;
        }
    
        static void insert(int x,int index){
            while(x < minHeap[index/2]){
                minHeap[index] = minHeap[index/2];
                index /= 2;
            }
            minHeap[index] = x;
        }
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n,m,x;
            n = in.nextInt();
            m = in.nextInt();
            for(int i=1; i<=n; i++){
                x = in.nextInt();
                CreateHeap.insert(x, i);
            }
    
            int pos = 1;
            for(int i=1; i<=m; i++){
                pos = in.nextInt();
                while(pos != 0){
                    System.out.print(minHeap[pos]);
                    if(pos != 1){
                        System.out.print(" ");
                    }
                    pos /= 2;
                }
                System.out.println();
            }
    
        }
    
    }
    

    结果因为java效率低,超时了。。
    - 我的代码二(方法一 C语言版)

    #include<stdio.h>
    #include<stdlib.h>
    
    #define capicity 1001
    #define minNum -10001
    
    int minHeap[capicity];
    
    void insetHeap(int x,int index)
    {
        while(x < minHeap[index/2])
        {
            minHeap[index] = minHeap[index/2];
            index /= 2;
        }
        minHeap[index] = x;
    }
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
    
        minHeap[0] = minNum;
        int i,x;
        for(i=1; i<=n; i++)
        {
            scanf("%d",&x);
            insetHeap(x,i);
        }
    
        int pos;
        for(i=1; i<=m; i++)
        {
            scanf("%d",&pos);
            while(pos){
                printf("%d",minHeap[pos]);
                if(pos != 1)    printf(" ");
                pos /= 2;
            }
            printf("\n");
        }
    
        return 0;
    } 
    

    通过了

    下面给出构建最大堆的函数代码,看懂思想就很容易写出来。不过要注意的是该题不能运用这个方法,因为这样构造出来的堆和一个个插入构造出来的堆结构不一定相同,那么输出的顺序就不同。

    /*----------- 建造最大堆 -----------*/
    void PercDown( MaxHeap H, int p )
    { /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */
        int Parent, Child;
        ElementType X;
    
        X = H->Data[p]; /* 取出根结点存放的值 */
        for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
            Child = Parent * 2;
            if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
                Child++;  /* Child指向左右子结点的较大者 */
            if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
            else  /* 下滤X */
                H->Data[Parent] = H->Data[Child];
        }
        H->Data[Parent] = X;
    }
    展开全文
  • 2020-10-12 18:35:38
    对于堆中的任意一个元素,其小于其两个儿子,所以根节点为最小值 基本操作: down操作:对大元素进行下移 up操作:对小元素进行上移 功能: 1、插入一个属 2、取出最小值 3、删除最小值 4、修改任意一个元素 5、删除...

    基本知识

    存储:
    定义一个数组,第一个节点表示根节点
    对于任意一个节点x,2x为其左儿子,2x+1为其右儿子

    堆是一个完全二叉树,除最后一行的元素外,其他元素均非空,最后一行从左到右依次排布

    对于堆中的任意一个元素,其小于其两个儿子,所以根节点为最小值

    基本操作:
    down操作:对大元素进行下移
    up操作:对小元素进行上移

    功能:
    1、插入一个数
    2、取出最小值
    3、删除最小值
    4、修改任意一个元素
    5、删除任意一个元素

    题目

    堆排序

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int h[N], s;
    void down(int u)
    {
        int t = u;
        if (u * 2 <= s && h[u * 2] < h[t]) //与左儿子比较大小
            t = u * 2;
        if (u * 2 + 1 <= s && h[u * 2 + 1] < h[t]) //与右儿子比较大小
            t = u * 2 + 1;
        if (u != t) //如果值不同说明这个数应该存在下面一个点
        {
            swap(h[u], h[t]);
            down(t); //再次递归处理这个数
        }
    }
    void up(int u)
    {
        while (u / 2 && h[u / 2] > h[u]) //,完全二叉树一个点只有两个儿子,所以上移不需要考虑左右的问题
        {
            swap(h[u / 2], h[u]);
            u = u / 2;
        }
    }
    int main()
    {
        int n, m;
        cin >> n >> m;
        s = n;
        for (int i = 1; i <= n; i++)
            cin >> h[i];
        for (int i = n / 2; i ; i--)
            down(i);
        while(m--)
        {
            cout<<h[1]<<" ";
            h[1]=h[s]; //将最后一个值移动到根节点再次进行down操作,因为对尾节点操作较为容易
            s--; //记得操作后堆中元素--
            down(1);
        }
        return 0;
    }
    
    展开全文
  • 1)堆中任意节点的值总是大于或小于其子节点的值; 2)堆是一棵完全树。 二叉堆又被称为优先队列,任意节点不大于其子节点的堆称为最小堆或最小优先队列,反之称为最大堆或最大优先队列。 一般用数组存储,且数组...

    二叉堆

    二叉堆是一棵完全二叉树,树上的每一个节点对应数组的每个元素。除了最底层外,该树是完全充满的,而且是从左向右填充。

    满足两个性质:
    1)堆中任意节点的值总是大于或小于其子节点的值;
    2)堆是一棵完全树。

    二叉堆又被称为优先队列,任意节点不大于其子节点的堆称为最小堆或最小优先队列,反之称为最大堆或最大优先队列。

    一般用数组存储,且数组下标0的位置不存数据,直接从1开始
    在这里插入图片描述

    优先队列

    优先级队列在插⼊或者删除元素的时候,需要调整元素位置, 保证底层二叉堆的性质
    优先级队列有两个主要 API, 分别是插⼊⼀个元素(insert) 和删除堆顶元素(delHeapTop)

    • C++实现代码:

    采用模板实现,实例化时,向构造函数传入 bool cmp(t1,t2);
    当函数 bool cmp(t1,t2),若t1>t2,返回true, 则是大顶堆
    当函数 bool cmp(t1,t2),若t1<t2,返回true, 则是小顶堆

    关于函数包装器function,参考:https://www.cnblogs.com/Braveliu/p/12387684.html

    #include<iostream>
    #include<string>
    #include<functional>
    #include<vector>
    #include<exception>
    using namespace std;
    
    /*说明:
    * cmp可以是一个函数/函数模板,或者一个函数对象/函数对象模板
    * 函数对象指定义了operator()操作符重载的类实例化的对象
    * cmp的参数(T,T),返回值bool
    * 对于cmp(t1,t2),若t1>t2,返回true,则是大顶堆
    * 对于cmp(t1,t2),若t1<t2,返回true,则是小顶堆
    */
    
    template<typename T>
    class priorityQueue{
    public:
        vector<T> Q;
        function<bool(T,T)> CMP;
    
    public:
        explicit priorityQueue(function<bool(T,T)> cmp):Q(1,0),CMP(cmp)
        {
        }
        ~priorityQueue(){
        }
    
    public:
        /*返回当前队列队首元素,但不删除它*/
        T heapTop(){
            return Q[1];
        }
    
        /*插入元素*/
        void insert(T x){
            //先将元素插到最后
            Q.push_back(x);
            //然后让他上浮到正确的位置
            swim(qsize());//qsize()返回最后位置
        }
    
        /*删除并返回当前队列中队首的元素
        * ⽅法先把堆顶元素 A 和堆底最后的元素 B 对调, 然后删除 A,
        * 最后让 B 下沉到正确位置
        */
        T delHeapTop(){
            if(qsize()==0)//越界
                throw out_of_range("priorityQueue is empty");
            //堆顶元素
            T max=Q[1];
            //把堆顶元素换到最后,删除之
            swap(1,qsize());
            Q.pop_back();
            //让Q[1]下沉到正确位置
            sink(1);
            return max;
        }
    
        /*返回堆大小*/
        int qsize(){
            return Q.size()-1;//去掉头一个位置
        }
    
    private:
        /*上浮第k个元素,以维护堆性质*/
        void swim(int k){
             while(k>1 && CMP(Q[k],Q[parent(k)])){
                //大顶堆:如果第k个元素比上层大 //小顶堆:如果第k个元素比上层小
                //将k换上去
                swap(parent(k),k);
                k=parent(k);
             }
        }
    
        /*下沉第k个元素,以维护堆性质*/
        void sink(int k){
            while(left(k)<=qsize()){
                //先假设左孩子
                int older=left(k);
                //如果右孩子存在,比一下大小
                if(right(k)<=qsize() && CMP(Q[right(k)],Q[older]))
                    older=right(k);
                //大顶堆:结点k比两孩子都大,就不必下沉了//小顶堆:结点k比两孩子都小,就不必下沉了
                if(CMP(Q[k],Q[older]))
                    break;
                //否则,下沉k结点
                swap(k,older);
                k=older;
            }
        }
        /*交换两个元素*/
        void swap(int i,int j){
            T temp=Q[i];
            Q[i]=Q[j];
            Q[j]=temp;
        }
        /*父结点索引*/
        int parent(int root){
            return root/2;
        }
        /*左孩子结点索引*/
        int left(int root){
            return root*2;
        }
        /*右孩子结点索引*/
        int right(int root){
            return root*2+1;
        }
    };
    
    template<class T>
    bool myMore(T t1,T t2){
        return t1>t2?true:false;
    }
    template<class T>
    bool myLess(T t1,T t2){
        return t1<t2?true:false;
    }
    
    int main(){
    //注意:在标准库中的头文件<queue>中的priority_queue,默认情况下用less表示大顶堆,
    //而用greater表示小顶堆,比如priority_queue<int,vector<int>,greater<int>> least;这在标准库中表示小顶堆
    //关于priority_queue的用法  
    //参考:https://blog.csdn.net/qq_35987777/article/details/106438221
    
        priorityQueue<int> maxPriorityQueue(myMore<int>);//大顶堆
        for(int i=1;i<10;i++)
            maxPriorityQueue.insert(i);
        int pSize=maxPriorityQueue.qsize();
        for(int j=0;j<pSize;j++)
            cout<<maxPriorityQueue.delHeapTop()<<" ";
    
        try{
            maxPriorityQueue.delHeapTop();//越界
        }catch(exception const& ex) {
            cerr <<endl<< "Exception: " << ex.what() <<endl;
        }
    
        priorityQueue<int> minPriorityQueue(myLess<int>);//小顶堆
        for(int i=1;i<10;i++)
            minPriorityQueue.insert(i);
        pSize=minPriorityQueue.qsize();
        for(int j=0;j<pSize;j++)
            cout<<minPriorityQueue.delHeapTop()<<" ";
    
        system("pause");
        return 0;
    }
    

    堆排序

    • 利用上面实现的优先队列很容易实现堆排序,把上面的main函数改为如下:
      时间复杂度:O(NlogN)O(N*logN)
      额外空间复杂度:O(N)O(N)
    int main(){
    
        priorityQueue<int> minPriorityQueue(myLess<int>);//小顶堆
        vector<int>nums{2,3,5,3,4,4,5,2,5};
        
        cout<<" before sort,nums= ";
        for(int i=0;i<nums.size();i++){
            cout<<nums[i]<<" ";
            minPriorityQueue.insert(nums[i]);
        }
        cout<<endl<<" before heapSort,nums= ";
        for(int j=0;j<nums.size();j++){
            nums[j]=minPriorityQueue.delHeapTop();
            cout<<nums[j]<<" ";
        }
        system("pause");
        return 0;
    }
    

    在这里插入图片描述

    • 这里还有一份左程云简化版的堆排序实现,
      时间复杂度O(N*logN),额外空间复杂度O(1)。
      给定一个数组,原地建大顶堆,同时对数组原地堆排序,

    这里堆是从下标0开始的,关于堆从下标0还是下标1开始,都可以,

    • 从0开始,i结点的左孩子2*i+1,右孩子2*i+2, index结点的父亲:(index-1)/2;
    • 从1开始,i结点的左孩子2*i,右孩子2*i+1, index结点的父亲:index)/2;

    堆排序的细节和复杂度分析
    时间复杂度O(N*logN),额外空间复杂度O(1)
    1,堆结构的heapInsert与heapify
    2,堆结构的增大和减少
    3,如果只是建立堆的过程,时间复杂度为O(N)
    4,优先级队列结构,就是堆结构

    建最大堆过程: 遍历数组,每次与自己父节点比较,大于父节点就与父节点交换,一直上浮到根节点为止

    提示:
    下标i节点的父节点下标(i-1)/2;
    下标为i的节点的左孩子为(2i+1),右孩子为2i+2;

    //函数含义:将数组arr中下标index的元素上浮到正确位置。
    void heapInsert(int arr[], int index)
    {
    	while (arr[index] > arr[(index - 1 )/ 2]) {
    		swap(arr[index], arr[(index - 1) / 2]);
    		index = (index - 1) / 2;
    	}
    }
    

    heapify函数将数组arr中下标为index处的元素下潜到正确位置

    //函数含义:将数组arr中下标为index处的元素下潜到正确位置
    void heapify(int arr[], int index, int heapSize) 
    {
    	int left = index * 2 + 1;
    	while (left < heapSize) {
    		int largest = left + 1 < heapSize && arr[left + 1] > arr[left]
    			? left + 1
    			: left;
    		largest = arr[largest] > arr[index] ? largest : index;
    		if (largest == index) {
    			break;
    		}
    		//某个孩子比较大,那个孩子的位置是largest
    		swap(arr[largest], arr[index]);
    		index = largest;//下潜到较大孩子节点
    		left = index * 2 + 1;//准备下次循环
    	}
    }
    
    
    • 对数组原地堆排序,额外空间复杂度O(1),时间复杂度O(n*logn)
    1. 先利用heapInsert原地建立大顶堆,根节点即为max
    2. 然后将根节点(max)与最后一个元素交换,同时将堆的尾部前移(因为第一次的max已经放到正确位置了),
    3. 然后比较新的根节点与左右孩子节点中的最大值,新根节点小于左右节点最大值,则交换;若交换发生,就一直下潜到最下层;(这个方法用于删除头节点也可以)

    这里有个值得初学者注意的点:

    一个数组int arr[]不是作为形参的话,sizeof(arr) / sizeof(*arr)就返回数组大小。

    一个数组若作为形参的话,因为数组本身不能复制,形参只是一个指针,所以无法在函数里面通过上面的方式计算数组大小,所以一般得传入一个形参arrSize表示数组大小

    void heapSort(int arr[],int arrSize)
    {
       	if (arrSize< 2)
    		return;
    	for (int i = 0; i < arrSize; i++) {
    		heapInsert(arr, i);//原地建立大顶堆
    	}
    
    	int heapSize = arrSize;
    	swap(arr[0], arr[--heapSize]);//首次max,换到数组尾部
    	while (heapSize > 0) {
    		heapify(arr, 0, heapSize);//在数组arr的前heapSize个元素中,将下标0处元素下潜
    		swap(arr[0], arr[--heapSize]);//下潜完毕,将头部元素换到下标--heapSize处
    	}
    }
    
    • 完整测试代码:
    #include<iostream>
    #include<vector>
    using namespace std;
    
    //建最大堆过程: 遍历数组,每次与自己父节点比较,大于父节点就与父节点交换,一直上浮到根节点为止
    //提示:下标i节点的父节点下标(i-1)/2;
    //下标为i的节点的左孩子为(2*i+1),右孩子为2*i+2;
    
    //函数含义:将数组arr中下标index的元素上浮到正确位置。
    void heapInsert(int arr[], int index)
    {
    	while (arr[index] > arr[(index - 1 )/ 2]) {
    		swap(arr[index], arr[(index - 1) / 2]);
    		index = (index - 1) / 2;
    	}
    }
    //函数含义:将数组arr中下标为index处的元素下潜到正确位置
    void heapify(int arr[], int index, int heapSize)
    {
    	int left = index * 2 + 1;
    	while (left < heapSize) {
    		int largest = left + 1 < heapSize && arr[left + 1] > arr[left]
    			? left + 1
    			: left;
    		largest = arr[largest] > arr[index] ? largest : index;
    		if (largest == index) {
    			break;
    		}
    		//某个孩子比较大,那个孩子的位置是largest
    		swap(arr[largest], arr[index]);
    		index = largest;//下潜到较大孩子节点
    		left = index * 2 + 1;//准备下次循环
    	}
    }
    
    
    void heapSort(int arr[],int arrSize)
    {
       	if (arrSize< 2)
    		return;
    	for (int i = 0; i < arrSize; i++) {
    		heapInsert(arr, i);//原地建立大顶堆
    	}
    
    	int heapSize = arrSize;
    	swap(arr[0], arr[--heapSize]);//首次max,换到数组尾部
    	while (heapSize > 0) {
    		heapify(arr, 0, heapSize);//在数组arr的前heapSize个元素中,将下标0处元素下潜
    		swap(arr[0], arr[--heapSize]);//下潜完毕,将头部元素换到下标--heapSize处
    	}
    }
    
    int main(){
        int nums[]={2,3,5,3,4,4,5,2,5};
        int numsSize=sizeof(nums)/sizeof(nums[0]);//数组元素个数
    
        cout<<" before sort,nums= ";
        for(int i=0;i<numsSize;i++){
            cout<<nums[i]<<" ";
        }
        cout<<endl<<" after heapSort,nums= ";
        heapSort(nums,numsSize);
        for(int j=0;j<numsSize;j++){
            cout<<nums[j]<<" ";
        }
    
        system("pause");
        return 0;
    }
    
    

    在这里插入图片描述

    标准库的make_heap(), pop_heap(), push_heap()

    头文件

    #include <algorithm> 
    
    • make_heap()是生成一个堆,大顶堆或小顶堆
    //默认生成大顶堆
    template <class RandomAccessIterator>
      void make_heap (RandomAccessIterator first, RandomAccessIterator last);
    //comp是greater时生成小顶堆,less时生成大顶堆
    template <class RandomAccessIterator, class Compare>
      void make_heap (RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp );
    
    • push_heap()是向堆中插入一个元素,并且使堆的规则依然成立
    //默认为大顶堆
    template <class RandomAccessIterator>
      void push_heap (RandomAccessIterator first, RandomAccessIterator last);
    //comp是greater时为小顶堆,less时为大顶堆
    template <class RandomAccessIterator, class Compare>
      void push_heap (RandomAccessIterator first, RandomAccessIterator last,
                       Compare comp);
    

    调用push_heap之前必须调用make_heap创建一个堆,首先调用push_back向容器中尾插入元素,然后再调用push_heap,它会使最后一个元素插到合适位置

    注意,push_heap中的comp和make_heap中的comp参数必须是一致的,不然会导致插入堆失败,最后一个元素还是在最后位置。

    • pop_heap()是在堆的基础上,弹出堆顶元素
    //默认为大顶堆
    template <class RandomAccessIterator>
      void pop_heap (RandomAccessIterator first, RandomAccessIterator last);
    //comp是greater时为小顶堆,less时为大顶堆
    template <class RandomAccessIterator, class Compare>
      void pop_heap (RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp);
    

    这里需要注意的是,pop_heap()并没有删除元素,而是将堆顶元素和容器最后一个元素进行了替换,如果要删除这个元素,还需要对容器进行pop_back()操作

    示例

    # include <iostream>
    # include <functional>
    # include <vector>
    # include <algorithm>
    
    using namespace std;
    
    void printVec(vector<int> nums)
    {
        for (int i = 0; i < nums.size(); ++i)
            cout << nums[i] << " ";
        cout << endl;
    }
    int main(void)
    {
        int nums_temp[] = {8, 3, 4, 8, 9, 2, 3, 4, 10};
        vector<int> nums(nums_temp, nums_temp + 9);
        cout << "make_heap之前: ";
        printVec(nums);
    
        cout << "(默认(less))make_heap: ";
        make_heap(nums.begin(), nums.end());
        printVec(nums);
    
        cout << "(less)make_heap: ";
        make_heap(nums.begin(), nums.end(), less<int> ());
        printVec(nums);
    
        cout << "(greater)make_heap: ";
        make_heap(nums.begin(), nums.end(), greater<int> ());
        printVec(nums);
    
        //先向容器插入一个数,之后在调用push_heap调整容器
        cout << "此时,nums为小顶堆 greater" << endl;
        cout << "push_back(3)" << endl;
        nums.push_back(3);
        
        cout << "默认(less)push_heap 此时push_heap失败: ";
        push_heap(nums.begin(), nums.end());
        printVec(nums);
        
        cout << "push_heap为greater 和make_heap一致,此时push_heap成功: ";
        push_heap(nums.begin(), nums.end(), greater<int>());
        printVec(nums);
        
        //先调用pop_heap将堆顶元素交换到容器末尾,然后调用容器的pop_back才能删除元素
        cout << "(greater)pop_heap: ";
        pop_heap(nums.begin(), nums.end(),greater<int>());
        printVec(nums);
        
        cout << "pop_back(): ";
        nums.pop_back();
        printVec(nums);
    
        system("pause");
        return 0;
    }
    
    
    展开全文
  • 的定义:有如下性质的完全二叉树:任意节点X所处的项的关键字大于或等于以X为根的子数的所有节点出的项的关键字。意义在于,在数据结构,其常常被用作优先级队列的结构,其意义是每次队列获取的元素,总是...

    堆的定义:有如下性质的完全二叉树:任意节点X所处的项的关键字大于或等于以X为根的子数中的所有节点出的项的关键字。

    意义在于,在数据结构中,其常常被用作优先级队列的结构,其意义是每次从队列中获取的元素,总是最满足某个条件的;比如最大的元素;再例如先进先出队列所满足的特定条件就是,具备放入队列时间最早的那个元素。

    堆实现的主要操作就是 插入和 删除(移除并获取那个最符合条件的元素)。先简单描述下逻辑

    插入:1.将新插入的元素,放置到队列的尾部。

    2.若该元素大于其父节点,两个元素互换。(上移操作)

    3.循环第2步,直至该元素没有父节点或小于其父节点。

    删除:1.移掉顶部的节点。

    2.将队末的元素放置到顶部。

    3.该节点与其子节点中较大的那个比较,若小于它,则交换位置,(下移操作)

    4.循环第3步,直到叶节点或不再比其子节点中较大那个小。

    若是最小堆,比较都反过来。

    在实现的中,用ArrayList作为其内部容器,首先因为ArrayList基于数组,方便快速定位,父节点与子节点的关系只需要计算下就可以得出: 【2*index + 1 】或【 (index -1)/2】, 其次ArrayList以及自动实现了写基础操作,扩容、判空、容器大小等。下面是代码,若有更好的实现,欢迎指点 :)

    public class Heap> {

    ArrayList items;

    int cursor; //用于计数

    public Heap(int size){

    items = new ArrayList(size);

    cursor = -1;

    }

    public Heap(){

    items = new ArrayList();

    cursor = -1;

    }

    /**

    * 上移操作

    * @param index 被上移元素的起始位置。

    */

    void siftUp(int index){

    T intent = items.get(index);

    while(index > 0){

    int pindex = (index - 1)/2;

    T parent = items.get(pindex);

    if(intent.compareTo(parent) > 0){//上移的条件,比父节点大

    items.set(index, parent);

    index = pindex;

    }else break;

    }

    items.set(index, intent);

    }

    /**

    * 下移操作

    * @param index 被下移的元素的起始位置

    */

    void siftDown(int index){

    T intent = items.get(index);

    int l_index = 2*index +1;

    while(l_index < items.size()){

    T maxChild = items.get(l_index);

    int max_index = l_index;

    int r_index = l_index + 1;

    if(r_index < items.size()){

    T rightChild = items.get(r_index);

    if(rightChild.compareTo(maxChild) > 0){

    maxChild = rightChild;

    max_index = r_index;

    }

    }

    if(maxChild.compareTo(intent) > 0){

    items.set(index, maxChild);

    index = max_index;

    l_index = index * 2 + 1 ;

    }else break;

    }

    items.set(index, intent);

    }

    public void add (T item){

    //先添加到最后

    items.add(item);

    //循环上移,以完成重构

    siftUp(items.size() -1);

    }

    public T deleteTop(){

    if(items.isEmpty()){

    throw new NoSuchElementException();

    }

    //先获取顶部节点

    T maxItem = items.get(0);

    T lastItem = items.remove(items.size() -1 );

    if(items.isEmpty()){

    return lastItem;

    }

    //将尾部的节点放置顶部,下移,完成重构

    items.set(0, lastItem);

    siftDown(0);

    return maxItem;

    }

    public T next(){

    if(cursor < 0 || cursor == (items.size() -1)){

    return null;

    }

    cursor++;

    return items.get(cursor);

    }

    public T first(){

    if (items.size() == 0 ) return null;

    cursor = 0;

    return items.get(0);

    }

    public boolean isEmpty(){

    return items.isEmpty();

    }

    public int size(){

    return items.size();

    }

    public void clear(){

    items.clear();

    }

    }

    原创博客,转载请注明

    http://my.oschina.net/BreathL/blog/71602

    展开全文
  • 堆 图 字符串匹配算法(查找算法)堆:...堆中插入元素:堆化操作:下往上,上往下 1.插入底部;2.堆化操作,调换(当前结点和父结点),直到满足 2.删除堆顶元素 堆 时间复杂度:o(logn) 堆排序时间复杂度:o(n
  • 删除任意节点:删除节点后,找到该节点的右子树最小值,让他顶替该节点的位置,并在原来的位置上删除这个最 小值 用链表来实现set集合复杂度是O(n),而用二分搜索树来实现Set,复杂度是O(logn):其实是O(h),h...
  • 优先队列是至少允许插入和删除最小者这两个操作的数据结构。其中,对于优先队列的实现,二叉堆是很常见的。  堆是一棵被完全填满的二叉树,可能例外是底层,底层上的... 堆的性质,在堆中,对于每一个节点X,X的父
  • 优先队列是至少允许插入和删除最小者这两个操作的数据结构。其中,对于优先队列的实现,二叉堆是很常见的。 堆是一棵被完全填满的二叉树,可能例外是底层,... 堆的性质,在堆中,对于每一个节点X,X的父亲中的关...
  • 数据结构-实现

    2013-06-17 16:55:04
     的定义:有如下性质的完全二叉树:任意节点X所处的项的关键字大于或等于以X为根的子数的所有节点出的项的关键字。  意义在于,在数据结构,其常常被用作优先级队列的结构,其意义是每次队列获取的元素...
  • 堆堆的存储推排序基本操作down(x)逻辑up(x)逻辑插入一个数求集合的最小值删除最小值删除任意一个元素(stl无法直接实现)修改任意一个元素(stl无法直接实现)代码思路函数逻辑 定义 维护一个数据集合。是...
  • 二叉查找树

    2015-09-08 09:12:18
    虽然在需要优先级队列的应用程序中,堆非常合适,但它并不适用删除任意元素的应用,具有n个元素的堆中删除任意元素的时间开销为O(n),并且查询任意元素的时间开销也是O(n),因此当进行插入,删除和查找操作,二叉...
  • 172 删除字符串的特定字符 173 求解符号方程 174 计算标准差 175 求取符合特定要求的素数 176 统计符合特定条件的数 177 字符串倒置 178 部分排序 179 产品销售记录处理 180 特定要求的字符编码 181 求解...
  • 时间复杂性 算法的时间复杂性计算如下把所有字符插入堆中需要时间(n)从堆中删除两个元素和加一个新元素需要的时间是O(logn)因为这被重复n-1次for循环需要的所有时间是O(nlogn)就得到算法的时间复杂性是O(nlogn) * ...
  • 数组在堆中有一块连续的存储空间,首地址知道后,就能快速遍历任意元素;增删慢是因为当中间插入或者删除元素时,会造成元素后面的所有元素地址的改变 链表: 链表具有增删快遍历慢的特点。链表中各个元素的内存空间...
  • 值类型与引用类型

    千次阅读 2019-09-03 23:10:58
    一:C#语言的数据类型 C#的数据类型分为两类:值类型(基本的数据类型)和引用类型值类型:byte,int,float,bool,struct..... ...栈只能栈顶插入或删除元素,类似于桶装的薯片,先进后出 能够以任意顺序...
  • C++学习笔记11 STL list

    2017-09-08 20:37:22
    STL list 双向链表list就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的,通过指针来进行数据的访问。这个特点使得它的随即存取变的非常没有效率,因此它没有提供[]操作...
  • 总结需要经常随机访问请用vector2.listlist就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的,通过指针来进行数据的访问,这个特点使得它的随机存取变的非常没有效率,因此...
  • 数据结构

    2020-04-27 07:30:50
    内存连续,数组元素通过数组下标进行访问,数组下标0开始。 优点: 索引查询元素速度快。 缺点: 无法扩容 。 只能存储一种类型的数据 插入,删除,要移动其他元素。 链表 链表的存储单元不是连续的,每个节点...
  • stl的实现原理

    千次阅读 2014-08-09 10:29:17
    list就是双向链表,元素也是在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的,通过指针来进行数据的访问,这个特点使得它的随机存取变的非常没有效率,因此它没有提供[]操作符的重载。但由于链表...
  • 默认值: NLS_TERRITORY 获得 nls_time_tz_format: 说明: 指定一对值 (UTC,TZD), 设置 TIME WITH TIME ZONE 数据类型的默认值, 该数据类型包含 HOUR, MINUTE, SECOND, TIMEZONE_HOUR 和 TIMEZONE_MINUTE 这几个...
  • 算法

    2020-09-16 22:49:08
    1,二叉树多个节点的最近公共祖先,时间复杂度 2,rand5()转rand7() ...11,给定数组,每个元素代表一个木头的长度,木头可以任意截断,木头截出至少k个相同长度为m的木块,已知k,求max(m) 12,给定数组[1,
  • 例如,在一维数组[21,46,24,99,57,77,86],查找数据元素99,首先第1个元素21开始进行比较,比较结果与要查找的数据不相等,接着与第2个元素46进行比较,以此类推,当进行到与第4个元素比较时,它们相等,...
  • 数据结构实验

    2012-04-13 09:55:47
    1.任意输入队列长度和队列元素值,构造一个顺序循环队列,对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。 2.约瑟夫环的实现:设有n个人围坐在圆桌周围,现某个位置 i 上的人开始报数,数到 ...
  • 每输出一个字符号,就将队头指针前移,将它缓冲队列中删除。假设有两个进程同时存在于一个应用程序中,第一个进程连续在屏幕上显示字符“X”,第二个进程不断检查键盘上是否有输入,若有则读入用户键入的字符,将...
  • javascript入门笔记

    2018-05-15 15:01:07
    1、弹框,分两次输入两个数字,分别保存在 a 和 b 2、如果 a 大于 b的话 ,则交换两个数字的位置 使用 短路&&,扩展赋值运算符,位运算 4、条件运算符(三目运算) 单目(一元)运算符 :++,--,! 双目(二元)...
  • 实例137 获取鼠标指针在任意位置的颜色值 216 实例138 图片浏览器 218 实例139 转换图片格式 219 实例140 绘制石英钟 221 实例141 画图程序 222 实例142 屏幕抓图程序 224 实例143 屏幕放大镜 225   第2篇 ...
  • 200个经典C程序【源码】

    千次下载 热门讨论 2013-08-08 10:48:40
    172 删除字符串的特定字符 173 求解符号方程 174 计算标准差 175 求取符合特定要求的素数 176 统计符合特定条件的数 177 字符串倒置 178 部分排序 179 产品销售记录处理 180 特定要求的字符编码 181 求解...
  • (62) 栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是(D) A. ABCED B. DBCEA C. CDABE D. DCBEA (63) 线性表的顺序存储结构和线性表的链式存储结构分别是(B) A. 顺序...

空空如也

空空如也

1 2 3 4
收藏数 67
精华内容 26
关键字:

从堆中删除任意元素