数据结构 ||大根堆的实现

建堆(建大堆)

• 算法思想
• 1.将指定数组的相关属性拷贝给目标堆
• 2.针对堆数组向满足堆性质的方向调整
• 代码实现

    void HeapInit(Heap<int>* heap,const T* array,int size){
      heap->_array=new T[size];
      heap->_size=size;
      memcpy(heap->_array,array,sizeof(T)*size);
      //用来将指定数组中的内容拷贝到堆数组空间中
      _CreateHeap(heap->_array,heap->_size); 
    }

    void _CreateHeap(T* array,int size){
      for(int i=(size-2)/2;i>=0;i--){
        AdjustDown(array,size,i);
      }
    }

向下调整

• 算法思想

• 1.拿到第一个非叶子结点的下标,

• 2.计算出左右孩子结点的下标,检查合法性

• 3.找出左右孩子中值较大的结点并与其父结点值比较大小

• 4.若左右孩子中较大孩子的结点值小于其父亲结点的值则不需要调整

• 5.若左右孩子中较大孩子的结点值大于其父亲结点的值则将较大孩子和父结点的值进行交换

• 代码实现

    void AdjustDown( T* array,int size,int parent){
      while(1){
        int left=2*parent+1;
        if(left>=size){
          return;
        }
        int max=left;
         int right=2*parent+2;     
        if(right<size && array[left]<array[right]){
          max=right;
        }

        if(array[parent] >=  array[max]){
          return;
        }

        Swap(array+parent,array+max);
        parent=max;
      }
    }

向上调整

• 算法思想

• 1.拿到孩子结点值的下标,检查其合法性

• 2.根据孩子的下标求出父亲结点的下标 [root]=[child-1]/2

• 3.判断下标child和下标root值对应的值的大小关系

• 4.若插入结点的值符合堆的性质则结束调整

• 5.若插入结点的值不符合堆的性质,则需要其与其父节点进行值的交换

• 6.一直调整到堆数组符合堆的性质为止

• 代码实现

    void AdjustUp(T* array,int  size,int child){

      while(child!=0){
        
        if(child>size){
          return;
        }
        int root=(child-1)/2;

        if(array[root]>=array[child]){
          return;
        }

        Swap(array+root,array+child);
        child=root;
      }
    }

堆的插入

• 算法思想
• 1.将新的值插入到堆的尾部
• 2.若其不满足堆的性质,对其进行向上调整
• 3.若其满足堆的性质,结束调整
• 代码实现

   void  HeapPush(Heap<T>* heap,T val){
      heap->_array[heap->_size]=val;
      heap->_size++;
      AdjustUp(heap->_array,heap->_size,heap->_size-1);
    }

堆的删除

• 算法思想
• 1.交换堆顶元素和最后一个元素的值
• 2.减少一个有效访问计数
• 3.从堆顶开始继续向下调整,直到符合堆的性质
• 代码实现

   void HeapPop(Heap<T>* heap){
     if(heap==nullptr){
       return;
     }

     Swap(heap->_array,&heap->_array[--heap->_size]);

     AdjustDown(heap->_array,heap->_size,0);
   }

整体实现

#pragma once 
#include<iostream>
#include<memory.h>

using namespace std;

template <class T>

class Heap{
  public:
    Heap(int size=T())
      :_array(nullptr)
       ,_size(size)
  {}

    void HeapInit(Heap<int>* heap,const T* array,int size){
      heap->_array=new T[size];
      heap->_size=size;
      memcpy(heap->_array,array,sizeof(T)*size);
      //用来将指定数据中的内容拷贝到堆数组空间中
      _CreateHeap(heap->_array,heap->_size); 
    }




    void PrintHeap(const Heap<T>* heap){
      if(heap==nullptr){
        return;
      }

      for(int i=0;i<heap->_size;i++){
        cout<<heap->_array[i]<< " ";
      }
      cout<<endl;
    }


   void  HeapPush(Heap<T>* heap,T val){
      heap->_array[heap->_size]=val;
      heap->_size++;
      AdjustUp(heap->_array,heap->_size,heap->_size-1);
    }

   void HeapPop(Heap<T>* heap){
     if(heap==nullptr){
       return;
     }

     Swap(heap->_array,&heap->_array[--heap->_size]);

     AdjustDown(heap->_array,heap->_size,0);
   }

   void Heap_Find(const Heap<T>* heap){
     int val=0;
    
     cout<<"请输入您要差找的值:";
     cin>>val;
     bool   index=false;

     for(int i=0;i<heap->_size;i++){
       if(heap->_array[i]==val){
         index=true;
         break;
       }
     }

     if(index==false){
       cout<<"您所要查找的值不存在!"<<endl;
       return;
     }

     cout<<"您所要查找的值在该堆中!"<<endl;

   }


   T& Heap_Top(const Heap<T>* heap){
     cout<<heap->_array[0];
   }


   //堆排序
   void Heap_Sort(T* array,int size){
     _CreateHeap(array,size);
     for(int i=0;i<size;i++){
       Swap(array,array+(size-1-i));
       AdjustDown(array,size-1-i,0);
     }
   }

   
   void HeapModify(Heap<T>* heap){
     int val;
     cout<<"请输入要修改的值:";
     cin>>val;

     int  index=-1;

     for(int i=0;i<heap->_size;i++){
       if(heap->_array[i]==val){
         index=i;
         break;
       }
     }

     if(index==-1){
       cout<<"您所要修改的值不存在!"<<endl;
       return;
     }

     cout<<"请输入修改后的值:";
     cin>>val;
     heap->_array[index]=val;

     AdjustUp(heap->_array,heap->_size,index);
   }
  private:
    void _CreateHeap(T* array,int size){
      for(int i=(size-2)/2;i>=0;i--){
        AdjustDown(array,size,i);
      }
    }

    void Swap(T* a,T* b){
      T tmp=*a;
      *a=*b;
      *b=tmp;
    }

    void AdjustDown( T* array,int size,int parent){
      while(1){
        int left=2*parent+1;
        if(left>=size){
          return;
        }



        int max=left;
         int right=2*parent+2;     
        if(right<size && array[left]<array[right]){
          max=right;
        }

        if(array[parent] >=  array[max]){
          return;
        }

        Swap(array+parent,array+max);
        parent=max;
      }
    }


    void AdjustUp(T* array,int  size,int child){

      while(child!=0){
        
        if(child>size){
          return;
        }
        int root=(child-1)/2;

        if(array[root]>=array[child]){
          return;
        }

        Swap(array+root,array+child);
        child=root;
      }
    }
  private:
    T* _array;
    int _size;
};

测试代码

#include"BinaryHeap.hpp"

void TestHeap(){
  int array[]={1,2,3,4,5,6,7,8,9};
  size_t size=sizeof(array)/sizeof(array[0]);
  Heap<int> heap;
  heap.HeapInit(&heap,array,size);
  heap.PrintHeap(&heap);
  heap.HeapPush(&heap,100);
  heap.PrintHeap(&heap);
  heap.HeapPop(&heap);
  heap.PrintHeap(&heap);

  heap.HeapModify(&heap);
  heap.PrintHeap(&heap);

  heap.Heap_Find(&heap);
  heap.Heap_Sort(array,size);
  heap.PrintHeap(&heap);
}

int main(){
  TestHeap();
  return 0;
}

测试结果展示

最后

以上就是单身板凳最近收集整理的关于数据结构 ||大根堆的实现的全部内容，更多相关数据结构内容请搜索靠谱客的其他文章。