shell复制代码curl -XPOST "http://127.0.0.1:9200/_flush/synced"

shell复制代码curl -XPOST "http://127.0.0.1:9200/demo/_flush/synced"

shell复制代码curl -X POST "http://127.0.0.1:9200/demo/_forcemerge"

shell复制代码curl -XPUT "http://127.0.0.1:9200/demo/_settings" -H 'Content-Type: application/json' -d'
{
  "index.max_result_window": "1000000"
}'

shell复制代码curl -XGET "http://127.0.0.1:9200/demo/_search?scroll=10s" -H 'Content-Type: application/json' -d'
{
  "size": 20, 
  "query": {
    "match_all": {}
  }
}'

json复制代码{
  "_scroll_id": "i1BOVdVWjJyU...",
  ... //省略
}

shell复制代码curl -XGETY "http://127.0.0.1:9200/_search/scroll" -H 'Content-Type: application/json' -d'
{
    "scroll" : "10s", 
    "scroll_id" : "i1BOVdVWjJyU..." 
}'

shell复制代码curl -XDELETE "http://127.0.0.1:9200/_search/scroll" -H 'Content-Type: application/json' -d'
{
    "scroll_id" : "i1BOVdVWjJyU..."
}'

shell复制代码curl -XGET "http://127.0.0.1:9200/demo/_search" -H 'Content-Type: application/json' -d'
{
  "from": 0,//from 永远从0开始
  "size": 10,
  "query": {
    "match_all": {}
  },
  "search_after": [ //初次不传，后续使用上次最后元素的排序值作为参数
    674688494483205
  ],
  "sort": [
    {
      "_id": { //稳定排序，建议最后排序字段用 _id
        "order": "desc"
      }
    }
  ]
}'

ini复制代码输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

 

提示：

    每个链表中的节点数在范围 [1, 100] 内
    0 <= Node.val <= 9
    题目数据保证列表表示的数字不含前导零

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

java复制代码/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int cc = 0;
        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0:l1.val;
            int y = l2 == null ? 0:l2.val;
            int sum = x + y + cc;
            cc = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (cc == 1) cur.next = new ListNode(cc);
        return pre.next;
    }
}

arduino复制代码//创建一个主题
void createTopic(final String key, final String newTopic, final int queueNum) throws MQClientException;
//根据 时间戳从队列中 查找其偏移量
long searchOffset(final MessageQueue mq, final long timestamp) throws MQClientException;
//查找该消息 队列中 最大的物理偏移量
long maxOffset(final MessageQueue mq) throws MQClientException;
//查找该消息队列中最小物理偏移量。
long minOffset(final MessageQueue mq) throws MQClientException;
//获取最早的存储消息时间
long earliestMsgStoreTime(final MessageQueue mq) throws MQClientException;
//根据消息偏移量查找消息
MessageExt viewMessage(final String offsetMsgId) throws RemotingException, MQBrokerException, InterruptedException, MQClientException;
//根据条件查询消息
QueryResult queryMessage(final String topic, final String key, final int maxNum, final long begin, final long end) throws MQClientException, InterruptedException;
//根据 主题 与 消息ID 查找消息 。
MessageExt viewMessage(String topic, String msgId) throws RemotingException, MQBrokerException, InterruptedException, MQClientException;

java复制代码//启动
void start() throws MQClientException;
 //关闭
void shutdown();
//根据topic获取对应队列信息
List<MessageQueue> fetchPublishMessageQueues(final String topic) throws MQClientException;
//同步-消息发送
SendResult send(final Message msg, final MessageQueue mq) throws MQClientException,RemotingException, MQBrokerException, InterruptedException;
//异步-消息发送
void send(final Message msg, final MessageQueueSelector selector, final Object arg, final SendCallback sendCallback) throws MQClientException, RemotingException, InterruptedException;
//同步-选择队列消息发送
SendResult send(final Message msg, final MessageQueueSelector selector, final Object arg, final long timeout) throws MQClientException, RemotingException, MQBrokerException,InterruptedException;
//单向-消息发送    
void sendOneway(final Message msg, final MessageQueue mq) throws MQClientException, RemotingException, InterruptedException;
//事务消息-发送
TransactionSendResult sendMessageInTransaction(final Message msg, final Object arg) throws MQClientException;
//批量消息-发送   
SendResult send(final Collection<Message> msgs) throws MQClientException, RemotingException, MQBrokerException, InterruptedException;

typescript复制代码//nameServer-地址，默认从：系统属性:rocketmq.namesrv.addr 或 环境变量:NAMESRV_ADDR 中获取
private String namesrvAddr = System.getProperty(MixAll.NAMESRV_ADDR_PROPERTY, System.getenv(MixAll.NAMESRV_ADDR_ENV));
//实例名字，默认：DEFAULT 或者 系统属性-rocketmq.client.name
private String instanceName = System.getProperty("rocketmq.client.name", "DEFAULT");
//构建 mq客户端的 id,例子:ip@instanceName@unitName : 172.16.62.75@19312@unitName
public String buildMQClientId() {
    StringBuilder sb = new StringBuilder();
    sb.append(this.getClientIP());
    sb.append("@");
    sb.append(this.getInstanceName());
    if (!UtilAll.isBlank(this.unitName)) {
        sb.append("@");
        sb.append(this.unitName);
    }
    return sb.toString();
}

//设置namesrv地址
public void setNamesrvAddr(String namesrvAddr) {
    this.namesrvAddr = namesrvAddr;
}

java复制代码// 构造器
public DefaultMQProducer(final String producerGroup, RPCHook rpcHook) {
    this.producerGroup = producerGroup;
    defaultMQProducerImpl = new DefaultMQProducerImpl(this, rpcHook);
}
// 各种发送消息
public SendResult send(
    Message msg) throws MQClientException, RemotingException, MQBrokerException, InterruptedException {
    return this.defaultMQProducerImpl.send(msg);
}
// 启动方法
public void start() throws MQClientException {
    this.defaultMQProducerImpl.start();
    if (null != traceDispatcher) {
        try {
            traceDispatcher.start(this.getNamesrvAddr());
        } catch (MQClientException e) {
            log.warn("trace dispatcher start failed ", e);
        }
    }
}

kotlin复制代码/**
 * mq-producer 启动
 * @param startFactory
 * @throws MQClientException
 */
public void start(final boolean startFactory) throws MQClientException {
    switch (this.serviceState) {
        case CREATE_JUST:
            // 0-服务状态设置
            this.serviceState = ServiceState.START_FAILED;
            //1-检测配置
            this.checkConfig();
            //2-并改变生产者的 instanceName为进程 ID。
            if (!this.defaultMQProducer.getProducerGroup().equals(MixAll.CLIENT_INNER_PRODUCER_GROUP)) {
                this.defaultMQProducer.changeInstanceNameToPID();
            }
            //3-创建 MQClientlnstance实例
            this.mQClientFactory = MQClientManager.getInstance().getAndCreateMQClientInstance(this.defaultMQProducer, rpcHook);
            //4-向 MQClientlnstance注册生产者。
            boolean registerOK = mQClientFactory.registerProducer(this.defaultMQProducer.getProducerGroup(), this);
            if (!registerOK) {
                this.serviceState = ServiceState.CREATE_JUST;
                throw new MQClientException("The producer group[" + this.defaultMQProducer.getProducerGroup()
                    + "] has been created before, specify another name please." + FAQUrl.suggestTodo(FAQUrl.GROUP_NAME_DUPLICATE_URL),
                    null);
            }
            //5-默认topic信息缓存（ this.defaultMQProducer.getCreateTopicKey() =  'TBW102' ）
            this.topicPublishInfoTable.put(this.defaultMQProducer.getCreateTopicKey(), new TopicPublishInfo());
            //6-是否启动-mQClientFactory
            if (startFactory) {
                mQClientFactory.start();
            }

            log.info("the producer [{}] start OK. sendMessageWithVIPChannel={}", this.defaultMQProducer.getProducerGroup(),
                this.defaultMQProducer.isSendMessageWithVIPChannel());
            this.serviceState = ServiceState.RUNNING;//设置状态为 运行中
            break;
        case RUNNING:
        case START_FAILED:
        case SHUTDOWN_ALREADY:
            throw new MQClientException("The producer service state not OK, maybe started once, "
                + this.serviceState
                + FAQUrl.suggestTodo(FAQUrl.CLIENT_SERVICE_NOT_OK),
                null);
        default:
            break;
    }
    //7-发送心跳到所有broker
    this.mQClientFactory.sendHeartbeatToAllBrokerWithLock();
}

csharp复制代码private void checkConfig() throws MQClientException {
    Validators.checkGroup(this.defaultMQProducer.getProducerGroup());
    if (null == this.defaultMQProducer.getProducerGroup()) {
        throw new MQClientException("producerGroup is null", null);
    }
    //生产所属组 不能等于 DEFAULT_PRODUCER
    if (this.defaultMQProducer.getProducerGroup().equals(MixAll.DEFAULT_PRODUCER_GROUP)) {
        throw new MQClientException("producerGroup can not equal " + MixAll.DEFAULT_PRODUCER_GROUP + ", please specify another one.",
            null);
    }
}

csharp复制代码// 判断producerGroup是否等于CLIENT_INNER_PRODUCER
if (!this.defaultMQProducer.getProducerGroup().equals(MixAll.CLIENT_INNER_PRODUCER_GROUP)) {
    this.defaultMQProducer.changeInstanceNameToPID();
}

是调用ClientConfig#changeInstanceNameToPID
publicvoid changeInstanceNameToPID() {
    if (this.instanceName.equals("DEFAULT")) {
        this.instanceName = String.valueOf(UtilAll.getPid());
    }
}

ini复制代码private static MQClientManager instance = new MQClientManager();//-单列模式
private AtomicInteger factoryIndexGenerator = new AtomicInteger();//index的工厂
// MQClientInstance 缓存
private ConcurrentMap<String/* clientId */, MQClientInstance> factoryTable = new ConcurrentHashMap<String, MQClientInstance>();

//构建返回MQClientInstance
public MQClientInstance getAndCreateMQClientInstance(final ClientConfig clientConfig, RPCHook rpcHook) {
    String clientId = clientConfig.buildMQClientId();//构建mq客户端的 id
    MQClientInstance instance = this.factoryTable.get(clientId);
    if (null == instance) {
        instance = new MQClientInstance(clientConfig.cloneClientConfig(),
                this.factoryIndexGenerator.getAndIncrement(), clientId, rpcHook);
        MQClientInstance prev = this.factoryTable.putIfAbsent(clientId, instance);
        if (prev != null) {
            instance = prev;
            log.warn("Returned Previous MQClientInstance for clientId:[{}]", clientId);
        } else {
            log.info("Created new MQClientInstance for clientId:[{}]", clientId);
        }
    }
    return instance;
}

java复制代码//key:group,    value: 生产者
private final ConcurrentMap<String/* group */, MQProducerInner> producerTable = new ConcurrentHashMap<String, MQProducerInner>();
// 将当前生产者加入到 MQClientlnstance管理中
public boolean registerProducer(final String group, final DefaultMQProducerImpl producer) {
    if (null == group || null == producer) {
        return false;
    }
    MQProducerInner prev = this.producerTable.putIfAbsent(group, producer);
    if (prev != null) {
        log.warn("the producer group[{}] exist already.", group);
        return false;
    }
    return true;
}

arduino复制代码//key:topic value:TopicPublishInfo-路由相关信息，用于消息发送
private final ConcurrentMap<String/* topic */, TopicPublishInfo> topicPublishInfoTable =
    new ConcurrentHashMap<String, TopicPublishInfo>();

kotlin复制代码public class TopicPublishInfo {
    //是否是顺序消息
    private boolean orderTopic = false;
    //是否包含路由信息
    private boolean haveTopicRouterInfo = false;
    //该主题队列的消息队列
    private List<MessageQueue> messageQueueList = new ArrayList<MessageQueue>();
    //每选择一次消息 队列， 该值会自增1，如果 Integer.MAX_VALUE, 则重置为 0，用于选择消息队列。
    private volatile ThreadLocalIndex sendWhichQueue = new ThreadLocalIndex();
    //路由信息
    private TopicRouteData topicRouteData;
    //选择队列方法，lastBrokerName其实上一次发送失败的brokerName，如果不为空，本次选择队列发送所在的brokerName则选择其他的brokerName
    public MessageQueue selectOneMessageQueue(final String lastBrokerName) {
        if (lastBrokerName == null) {
            return selectOneMessageQueue();
        } else {
            //如果消息发 送再失败的话 ， 下次进行 消息队列选择 时规避上次 MesageQueue 所 在的 Broker， 否 则还 是 很有可能再次失败 。
            int index = this.sendWhichQueue.getAndIncrement();
            for (int i = 0; i < this.messageQueueList.size(); i++) {
                int pos = Math.abs(index++) % this.messageQueueList.size();
                if (pos < 0)
                    pos = 0;
                MessageQueue mq = this.messageQueueList.get(pos);
                if (!mq.getBrokerName().equals(lastBrokerName)) {
                    return mq;
                }
            }
            return selectOneMessageQueue();
        }
    }
    //直接用 sendWhichQueue 自增再获取值 ， 与当前路由 表 中消息 队列个数取模， 返回该位置的 MessageQueue(selectOneMessageQueue()方法)
    public MessageQueue selectOneMessageQueue() {
        int index = this.sendWhichQueue.getAndIncrement();
        int pos = Math.abs(index) % this.messageQueueList.size();
        if (pos < 0)
            pos = 0;
        return this.messageQueueList.get(pos);
    }
    //messageQueueList-长度大于0
    public boolean ok() {
        return null != this.messageQueueList && !this.messageQueueList.isEmpty();
    }
    //是否包含路由信息
    public boolean isHaveTopicRouterInfo() {
        return haveTopicRouterInfo;
    }

kotlin复制代码     MQClientInstance#start
    public void start() throws MQClientException {
        synchronized (this) {
            switch (this.serviceState) {
                case CREATE_JUST:
                    this.serviceState = ServiceState.START_FAILED;   //1>状态-设置启动失败
                    // If not specified,looking address from name server
                    if (null == this.clientConfig.getNamesrvAddr()) {  //2>判断nameSrvAddr地址是否为空，http获取nameSrvAddr
                        this.mQClientAPIImpl.fetchNameServerAddr();
                    }
                    // Start request-response channel : netty
                    this.mQClientAPIImpl.start();  // 3>启动netty相关
                    // Start various schedule tasks
                    this.startScheduledTask();   //4>【重要】启动相关定时任务
                    // Start pull service
                    this.pullMessageService.start();    //5>消费端相关，后续讲解
                    // Start rebalance service
                    this.rebalanceService.start();      //6>消费端相关，后续讲解
                    // Start push service
                    this.defaultMQProducer.getDefaultMQProducerImpl().start(false); //7>内部启动一个mqProducter，startFactory=false
                    log.info("the client factory [{}] start OK", this.clientId);
                    this.serviceState = ServiceState.RUNNING; >8 状态设置运行中
                    break;
                case RUNNING:
                    break;
                case SHUTDOWN_ALREADY:
                    break;
                case START_FAILED:
                    throw new MQClientException("The Factory object[" + this.getClientId() + "] has been created before, and failed.", null);
                default:
                    break;
            }
        }
    }

kotlin复制代码        public void sendHeartbeatToAllBrokerWithLock() {
        if (this.lockHeartbeat.tryLock()) {
            try {
                this.sendHeartbeatToAllBroker(); 1> 发送心跳到所有broker
                this.uploadFilterClassSource();  2> 更新过滤filterSource 可忽略不看
            } catch (final Exception e) {
                log.error("sendHeartbeatToAllBroker exception", e);
            } finally {
                this.lockHeartbeat.unlock();
            }
        } else {
            log.warn("lock heartBeat, but failed.");
        }
    }

python复制代码from flask import Flask
from flask_sqlalchemy import SQLAlchemy

app = Flask(__name__)

basedir = os.path.abspath(app.root_path)
app.config['SQLALCHEMY_DATABASE_URI'] = 'sqlite:///' + os.path.join(basedir, 'data.db')
app.config['SQLALCHEMY_TRACK_MODIFICATIONS'] = False

db = SQLAlchemy(app)

python复制代码from app import db


class User(db.Model):
    id = db.Column(db.Integer, primary_key=True)
    user_name = db.Column(db.String)
    password = db.Column(db.String)

python复制代码>>> from app import db  # 从app.py中导入db实例
>>> from model import *  # 从model.py中导入所有模型类
>>> db.create_all()  # 用db.create_all()创建数据库表

python复制代码>>> from app import db  # 从app.py中导入db实例
>>> from model import User   # 导入模型类User
>>> user1=User(user_name='tigeriaf', password='123456')  # 创建用户1
>>> user2=User(user_name='admin', password='123456')  # 创建用户2
# 添加新创建的对象到数据库会话中
>>> db.session.add(user1)
>>> db.session.add(user2)
# 将数据库会话提交，数据写入data.db文件
>>> db.session.commit()
# 测试
>>> print(user1.id)
1
>>> print(user2.id)
2

python复制代码# 查询全部
>>> User.query.all()
[<User 1>, <User 2>]
# 查询指定id的记录
>>> user1=User.query.get(1)
>>> user1.user_name
'tigeriaf'
# 查询条数
>>> User.query.count()
2
# 查询user_name为admin的用户
>>> User.query.filter_by(user_name='admin').all()
[<User 2>]

python复制代码>>> user2=User.query.get(2)
>>> user2.user_name
'admin'
>>> user2.user_name='张三'
>>> db.session.commit()
>>> user2.user_name
'张三'

python复制代码>>> db.session.delete(user2)
>>> db.session.commit()
>>> user2=User.query.get(2)
>>> print(user2)
None

python复制代码@app.route('/user', methods=['GET', 'POST'])
def user():
    if request.method == 'POST':
        user_name = request.form['user_name']
        password = request.form['password']
        user = User(user_name=user_name, password=password)
        db.session.add(user)
        db.session.commit()
        return 'user:{} add success! id:{}'.format(user_name, user.id)

    else:
        user_id = request.args.get('user_id')
        user = User.query.get(user_id)
        if user:
            return 'Hello user:{}!'.format(user.user_name)
        else:
            return 'failed'

c复制代码	struct Node* cur = head;
    if(!cur)
        return NULL;
    while(cur)
    {
        //每次我们都要malloc一个copy节点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        //开始给数据
        copy->val = cur->val;
        //开始插入
        copy->next = cur->next;
        cur->next = copy;
        //开始cur移动
        cur = copy->next;
    }

c复制代码 //节点copy好后开始random相链
    cur = head;
    while(cur)
    {
        //重新把之前开辟的节点给copy维护
        struct Node* copy = cur->next;
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;//上面的GIF的核心代码       
        cur = copy->next;  
    }

c复制代码 //开始一个一个尾插起来
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;
    cur = head;
    while(cur)
    {
        //重新把之前开辟的节点给copy维护
        struct Node* copy = cur->next;
        //这边你需要一个next来还原原来链表顺序，你不能用完人家对人家不负责任
        struct Node* next = copy->next;
        if(copyHead == NULL)
        {
            copyHead = copy;
            copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copy;
        }        
        cur->next = next;//这一步看你对原来链表负不负责任
        cur = next;
    }
    return copyHead;

c复制代码struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    if(!cur)
        return NULL;
    while(cur)
    {
        //每次我们都要malloc一个copy节点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        //开始给数据
        copy->val = cur->val;
        //开始插入
        copy->next = cur->next;
        cur->next = copy;
        //开始cur移动
        cur = copy->next;
    }
    //节点copy好后开始random相链
    cur = head;
    while(cur)
    {
        //重新把之前开辟的节点给copy维护
        struct Node* copy = cur->next;
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;//上面的GIF的核心代码       
        cur = copy->next;  
    }
    //开始一个一个尾插起来
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;
    cur = head;
    while(cur)
    {
        //重新把之前开辟的节点给copy维护
        struct Node* copy = cur->next;
        //这边你需要一个next来还原原来链表顺序，你不能用完人家对人家不负责任
        struct Node* next = copy->next;
        if(copyHead == NULL)
        {
            copyHead = copy;
            copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copy;
        }        
        cur->next = next;//这一步看你对原来链表负不负责任
        cur = next;
    }
    return copyHead;
}

typescript复制代码//这里的代码和原先的代码相比做了修改，去掉了map进行对于Stream中包含的元素使用给定的转换函数进行转换操作

public static Map<String, Object> parseMapForFilter(Map<String, Object> map) {
        if (map == null) {
            return null;
        } else {
            map = map.entrySet().stream()
                    .filter((e) -> checkValue(e.getValue()))
                    .collect(Collectors.toMap(
                            (e) -> (String) e.getKey(),
                            (e) -> e.getValue()
                    ));
        }
        return map;
    }
    
private static boolean checkValue(Object object) {

        if (object instanceof String && "".equals(object)) {
            return false;
        }

        if (null == object) {
            return false;
        }

        return true;


    }

csharp复制代码    public static void main(String[] args) {
        Map<String,Object> params = new HashMap<>(16);

        params.put("a","");
        params.put("b",null);
        params.put("c","c");

        params = MapUtil.parseMapForFilter(params);
        System.out.println(params);
        System.out.println(MapUtil.parseMapForFilter(null));
    }

ini复制代码{c=c}
null

scss复制代码public static Map<String, Object> parseMapForFilterByOptional(Map<String, Object> map) {

        return Optional.ofNullable(map).map(
                (v) -> {
                    Map params = v.entrySet().stream()
                            .filter((e) -> checkValue(e.getValue()))
                            .collect(Collectors.toMap(
                                    (e) -> (String) e.getKey(),
                                    (e) -> e.getValue()
                            ));

                    return params;
                }
        ).orElse(null);
    }

csharp复制代码    public static void main(String[] args) {
        Map<String, Object> params = new HashMap<>(16);

        params.put("a", "");
        params.put("b", null);
        params.put("c", "c");

        params = MapUtil.parseMapForFilterByOptional(params);

        System.out.println(params);
        System.out.println(MapUtil.parseMapForFilterByOptional(null));
    }

ini复制代码{c=c}
null

typescript复制代码    private static boolean checkValueByOptional(Object object) {
        return (Boolean) Optional.ofNullable(object)
                .filter((e) -> e instanceof String && e.equals("") ? false : true)
                .orElse(false);
    }

scss复制代码现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提：左右子树必须是一个堆 (包括大堆和小堆)，才能调整。

c复制代码int array[] = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37}

c复制代码int array[] = {27, 37, 28, 18, 19, 34, 65, 25, 49, 15}

c复制代码#include<stdio.h>

//实现父子交换的函数
void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
//实现调整
void AdjustDown(int* arr, int sz, int parent)
{
	//确定左孩子的下标
	int child = parent * 2 + 1;
	//孩子的下标超出数组的范围就停止
	while (child < sz)
	{
		//确定左右孩子中较小/大的那个
			//左孩子大于右孩子，所以让child记录较小孩子的下标 || (arr[child]<arr[child+1]记录较大孩子的下标)
		if (arr[child] > arr[child + 1] && child + 1 < sz)
		{
			child++; //(当只有一个左孩子时，会越界，且后面使用时会发生非法访问)
		}
		//判断父亲和小孩子
			//小孩子小于父亲，则交换，且继续调整 || (arr[child]>arr[parent]大孩子大于父亲，则交换，且继续调整)
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			//迭代
			parent = child;
			//重新确定左孩子的下标(当最后的叶子节点是parent时，这时去确定child会以读的方式越界，但可以不关心)
			child = parent * 2 + 1;
		}
		//小孩子大于父亲，则停止调整
		else
		{
			break;
		}
	}
}
//堆排序 -> 效率更高
void HeapSort(int* arr, int sz)
{
	//建堆
	int i = 0;
	//从最后一棵树开始调整，也就是最后一个节点的父亲
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
}
int main()
{
	//左右子树都为堆
	int arr1[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	//左右子树都为非堆
	int arr2[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };

	HeapSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
	int i = 0;
	for (i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
	{
		printf("%d ", arr1[i]);
	}

	printf("\n");

	HeapSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
	for (i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
	{
		printf("%d ", arr2[i]);
	}
	return 0;
}

scss复制代码因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明
(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)

c复制代码#pragma once

//头
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

typedef int HPDataType;

//C++ -> priority_queue 在C++里用的是优先级队列，其底层就是一个堆
//大堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//函数的声明
//交换
void Swap(int* px, int* py);
//向下调整
void AdjustDown(int* arr, int n, int parent);
//向上调整
void AdjustUp(int* a, int child);
//使用数组进行初始化
void HeapInit(HP* php, HPDataType* a, int n);
//回收空间
void HeapDestroy(HP* php);
//插入x，保持它继续是堆
void HeapPush(HP* php, HPDataType x); 
//删除堆顶的数据，保持它继续是堆
void HeapPop(HP* php);
//获取堆顶的数据，也就是最值
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//输出
void HeapPrint(HP* php);

c复制代码#include"Heap.h"


void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (arr[child] < arr[child + 1] && child + 1 < n)
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPrint(HP* php)
{
	assert(php);

	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//1、对于HeapCreate函数，结构体不是外面传进来的，而是在函数内部自己malloc空间，再创建的
/* 
HP* HeapCreate(HPDataType* a, int n)
{}
*/
//2、对于HeapInit函数，在外面定义一个结构体，把结构体的地址传进来
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php); 
	//malloc空间(当前数组大小一样的空间)
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//使用数组初始化
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;
	//建堆 
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	//空间不够，增容
	if (php->size == php->capacity)
	{
		HPDataType* temp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			php->a = temp;	
		}
		php->capacity *= 2;
	}
	//将x放在最后
	php->a[php->size] = x;
	php->size++;
	//向上调整
	AdjustUp(php->a, php->size - 1);
}
void HeapPop(HP* php)
{
	assert(php);
	//没有数据删除就报错
	assert(!HeapEmpty(php));
	//交换首尾
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	//向下调整
	AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	//没有数据获取就报错
	assert(!HeapEmpty(php));
	
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

c复制代码#include"Heap.h"

void TestHeap()
{
	int arr[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };
	HP hp;
	HeapInit(&hp, arr, sizeof(arr)/sizeof(arr[0]));
	HeapPrint(&hp);
	HeapPush(&hp, 18);
	HeapPrint(&hp);
	HeapPush(&hp, 98);
	HeapPrint(&hp);
	printf("\n\n");
	//将堆这数据结构实现好后，我们就可以利用这些接口实现排序
	while(!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));	
		HeapPop(&hp);
	}
	printf("\n");
	
}
int main()
{
	TestHeap();
	return 0;
}