`

阅读更多
在优先级队列的各种实现中,堆是最高效的一种数据结构

关键码:在各个数据记录中存在一个能够标识数据记录(或元素)的数据项,并将依据该数据项对数据进行组织,这个数据项就是关键码

最小堆:父结点总是小于等于子结点

最大堆:父结点总是大于等于子结点
MinHeap.h
#ifndef MINHEAP_H
#define MINHEAP_H

#include"../T3/PQueue.h"
#include<assert.h>

#define DefaultSize 10

template<typename E>
class MinHeap:public PQueue<E>{
public:
    MinHeap(int sz=DefaultSize);
    MinHeap(E arr[],int n);
    ~MinHeap(){delete[]heap;}
    bool Insert(const E &x);
    bool RemoveMin(E &x);
    bool IsEmpty() const{
        return currentSize==0?true:false;
    }
    bool IsFull()const{
        return currentSize==maxHeapSize?true:false;
    }
    void makeEmpty(){
        currentSize=0;
    }
    void display();
private:
    E *heap;
    int currentSize;
    int maxHeapSize;
    void siftDown(int start,int m);
    void siftUp(int start);
};

template<typename E>
MinHeap<E>::MinHeap(int sz)
{
    maxHeapSize=sz>DefaultSize?sz:DefaultSize;
    heap=new E[maxHeapSize];
    assert(heap!=NULL);
    currentSize=0;
}

/*
  最小堆的下滑高速算法
  */
template<typename E>
void MinHeap<E>::siftDown(int start, int m)
{
    int i=start,j=2*i+1;
    E temp = heap[i];
    while(j<=m){
        if(j<m&&heap[j]>heap[j+1]){
            j++;//指向子女中最小的一个
        }
        if(temp<=heap[j]){
            break;
        }else{
            heap[i]=heap[j];
            i=j;
            j=j*2+1;
        }
    }
    heap[i]=temp;
}

template<typename E>
MinHeap<E>::MinHeap(E arr[], int n)
{
    maxHeapSize=n>DefaultSize?n:DefaultSize;
    heap=new E[maxHeapSize];
    assert(heap!=NULL);
    for(int i=0;i<n;++i)
        heap[i]=arr[i];
    currentSize=n;
    int currentPos=(currentSize-2)/2;
    while(currentPos>=0){//自底向上逐步扩大
        siftDown(currentPos,currentSize-1);
        currentPos--;
    }
}

/*
  把start处的结点向上调整
  */
template<typename E>
void MinHeap<E>::siftUp(int start)
{
    int j=start,i=(j-1)/2;
    E temp=heap[j];
    while(j>0){
        if(heap[i]<=temp){
            break;
        }else{
            heap[j]=heap[i];
            j=i;
            i=(i-1)/2;
        }
    }
    heap[j]=temp;
}

template<typename E>
bool MinHeap<E>::Insert(const E &x)
{
    if(currentSize==maxHeapSize){
        cerr << "full" << endl;
        return false;
    }
    heap[currentSize]=x;
    siftUp(currentSize);
    currentSize++;
    return true;
}

template<typename E>
bool MinHeap<E>::RemoveMin(E &x)
{
    if(currentSize==0){
        cout << "empty" << endl;
        return false;
    }
    x=heap[0];
    currentSize--;
    siftDown(0,maxHeapSize-1);
    return true;
}

template<typename E>
void MinHeap<E>::display()
{
    for(int i=0;i<currentSize;++i)
        cout << heap[i] << " ";
}

#endif // MINHEAP_H


MinHeap.cpp
#include "MinHeap.h"

int main(){
    int a[10]={53,17,78,9,45,65,87,23};
    MinHeap<int> minHeap(a,8);
    minHeap.display();
}

9 17 65 23 45 78 87 53


分享到:
评论

相关推荐

    二叉堆(最小堆)+二项堆+斐波那契堆

    二叉堆、二项堆和斐波那契堆是数据结构中的重要概念,它们都是堆数据结构的不同变体,主要用于高效地实现某些特定操作,如查找最大或最小元素、优先队列以及各种排序算法。在C++编程语言中,理解和实现这些堆结构...

    华为交换机堆叠

    1. **配置交换机堆叠端口**:将出厂堆叠物理接口G0/0/28和G0/0/27分别加入到堆叠端口1和堆叠端口2,以实现所有堆叠交换机之间的堆叠端口交叉相连。初始状态下,所有成员交换机的堆叠ID均为默认的0,因此所有成员...

    堆排序算法源代码

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在本场景中,我们关注的是堆排序的源代码,它适用于openSUSE 11.4操作系统,并且是使用GCC version 4.5.1编译器编译的。在这个名为"sort...

    数据结构 堆的实现

    堆通常是一个完全二叉树,分为两种类型:最大堆和最小堆。在最大堆中,每个节点的值都大于或等于其子节点的值,而根节点是所有节点中最大的。相反,在最小堆中,每个节点的值小于或等于其子节点,根节点是最小的。...

    代码c++ 最大堆最小堆

    在计算机科学中,堆是一种特殊的树形数据结构,通常用于实现优先队列。堆有两种主要类型:最大堆和最小堆。最大堆确保每个父节点的值都大于或等于其子节点的值,而最小堆则相反,每个父节点的值都小于或等于其子节点...

    堆排序的c++实现代码

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,父节点的值总是大于或等于其子节点;而在小顶堆中,父节点的值总是小于或等于其子节点。在C++中,我们可以利用STL中的`...

    cisco交换机堆叠配置向导

    思科交换机堆叠配置向导 思科 StackWise 技术是思科公司的一种创新性的交换机堆叠技术,可以将多台交换机连接成一个单一的逻辑单元,提供高可靠性和高扩展性的交换解决方案。该技术可以将最多 9 台 Cisco Catalyst ...

    堆叠图_echarts_柱状堆叠图_

    在这个场景中,我们关注的是“堆叠图”和“柱状堆叠图”,这是ECharts中用于展现多组数据相互叠加效果的图表类型。这种图表可以有效地展示不同类别在总值中的占比,以及各个类别之间的相对关系。 堆叠图(Stacked ...

    华为交换机堆叠实例

    ### 华为交换机堆叠实例详解 #### 堆叠技术概述 堆叠技术是网络设备中一种高级互联方式,允许多台物理设备通过专用的堆叠端口连接在一起,形成逻辑上的一台设备。这不仅可以提升网络的扩展性和可用性,还能简化管理...

    数组堆操作,包括堆排序、堆插入、堆删除等

    数组堆操作是计算机科学中数据结构与算法的重要组成部分,主要涉及堆排序、堆插入、堆删除等核心概念。堆是一种特殊的树形数据结构,每个节点都有一个值,并且满足堆的性质:对于最大堆,父节点的值总是大于或等于其...

    c++ 大根堆和小根堆

    在计算机科学中,堆是一种特殊的树形数据结构,通常用于优先队列的实现。它具有以下两个关键特性:一是堆是一棵完全二叉树,即除了最底层外,其他层的节点都完全填满,且最底层的节点尽可能地集中在左边;二是堆有两...

    锐捷交换机去堆叠技术详解

    ### 锐捷交换机去堆叠技术详解 #### 第一章 厎叠方案概述 ##### 1.1 技术产生背景 随着数据中心规模的不断扩大和技术的发展,网络架构也经历了从传统三层到扁平化的演进过程。在这一过程中,网络设备之间的堆叠...

    H3C华为交换机堆叠配置大全

    【交换机堆叠】是指将多台交换机通过专用的堆叠模块和堆叠线连接在一起,形成一个逻辑上的单一设备,以增加端口数量、提高网络带宽和增强网络的可靠性。堆叠通常用于需要扩展端口或者提高网络性能的企业环境中。与之...

    堆的插入删除操作C++

    堆是一种特殊的树形数据结构,通常用于实现优先队列或高效地执行某些操作,如排序。在计算机科学中,堆可以分为两种主要类型:最大堆(Max-Heap)和最小堆(Min-Heap)。最大堆中,每个父节点的值都大于或等于其子...

    堆溢出和堆利用

    《堆溢出与利用》这本书深入探讨了计算机安全领域中的一个重要话题——堆溢出及其相关的攻击与防御策略。堆溢出是由于程序在分配和管理内存时,未能正确控制堆空间,导致数据超出预设边界,进而可能破坏相邻内存区域...

    堆排序 减治法——C++代码

    堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆通常被理解为一个完全二叉树,其中每个父节点的值都大于或等于(大顶堆)或小于或等于(小顶堆)其子节点的值。堆排序算法...

    H3C S6520交换机在现网环境下如何不断网配置堆叠(现网实战经验).pdf

    在IT网络环境中,核心交换机的堆叠是提高网络性能和冗余的重要手段。本文将详细阐述如何在现网环境中,特别是在不影响业务运行的情况下,配置H3C S6520系列交换机的IRF2(Intelligent Resilient Framework 2)堆叠。...

    石子合并 在一个圆形操场的四周摆放着 n 堆石子. 现要将石子有次序地合并成一堆, 规定每次只能选相邻的 2 堆石子合并成新的一堆, 并将新的一堆石子数记为该次合并的得分.

    首先,我们需要理解合并石子的过程实际上是在构建一棵由石子堆构成的树形结构,其中树的根节点代表最终合并成的一堆石子,而叶子节点则代表初始的石子堆。每一条从叶子节点到根节点的路径上的权值之和就是一种可能的...

    android图片堆叠效果实现

    在Android开发中,实现图片堆叠效果是一种常见的视觉设计需求,尤其在相册或图库应用中,这种效果可以提供一种独特的展示方式,使用户能够更直观地浏览多张图片。"图片堆叠"效果通常涉及到图像的重叠、旋转以及层次...

    内存中堆和栈的分配区别

    在计算机科学领域,内存管理是实现程序高效运行的关键技术之一,而其中的堆(Heap)与栈(Stack)是两种核心的内存分配方式。本文将深入探讨这两种内存区域的分配区别,以及它们在程序中的作用机制,帮助读者理解C/...

Global site tag (gtag.js) - Google Analytics