{"id":187,"date":"2025-07-20T20:21:11","date_gmt":"2025-07-20T12:21:11","guid":{"rendered":"http:\/\/www.tgwttt.xyz\/?p=187"},"modified":"2025-11-24T16:40:51","modified_gmt":"2025-11-24T08:40:51","slug":"%e5%a0%86%ef%bc%881%ef%bc%89","status":"publish","type":"post","link":"https:\/\/www.tgwttt.xyz\/?p=187","title":{"rendered":"\u5806\uff081\uff09"},"content":{"rendered":"\n<p>\u4ee5\u4e0b\u4ee3\u7801gitee\u4ed3\u5e93\u5730\u5740<a href=\"https:\/\/gitee.com\/tgwTTT\/data-structure\">tgw\/\u6570\u636e\u7ed3\u6784<\/a>\u3002<\/p>\n\n\n\n<p>\u5806\u7684\u6982\u5ff5\uff1a\u5982\u679c\u6709\u4e00\u4e2a\u5173\u952e\u7801\u7684\u96c6\u5408K = {k1 \uff0ck2 \uff0ck3 \uff0ck4\u2026\uff0ckn-1 }\uff0c\u628a\u5b83\u7684\u6240\u6709\u5143\u7d20\u6309\u5b8c\u5168\u4e8c\u53c9\u6811\u7684\u987a\u5e8f\u5b58\u50a8\u65b9\u5f0f\u5b58\u50a8 \u5728\u4e00\u4e2a\u4e00\u7ef4\u6570\u7ec4\u4e2d.<\/p>\n\n\n\n<p>\u5927\u6839\u5806\uff1a\u7236\u8282\u70b9\u5927\u4e8e\u6216\u7b49\u4e8e\u5b50\u8282\u70b9\u7684\u5806<\/p>\n\n\n\n<p>\u5c0f\u8ddf\u5806\uff1a\u7236\u8282\u70b9\u5c0f\u4e8e\u6216\u7b49\u4e8e\u7236\u8282\u70b9\u7684\u5806<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"555\" height=\"480\" src=\"http:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-36.png\" alt=\"\" class=\"wp-image-188\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-36.png 555w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-36-300x259.png 300w\" sizes=\"auto, (max-width: 555px) 100vw, 555px\" \/><\/figure>\n\n\n\n<p>\u5806\u7684\u5b9e\u73b0\uff1a<\/p>\n\n\n\n<p>\u9996\u5148\u5b9a\u4e49\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#define _CRT_SECURE_NO_WARNINGS 1\n#pragma once\n#include<stdio.h>\n#include<assert.h>\n#include<stdlib.h>\n#include<stdbool.h>\n#include<iostream>\ntypedef int HPDataType;\ntypedef struct Heap\n{\n\tHPDataType* a;\n\tint size;\n\tint capacity;\n}HP;\nvoid Swap(HPDataType* p1, HPDataType* p2);\nvoid AdjustUp(HPDataType* a, int child);\nvoid AdjustDown(HPDataType* a, int n, int parent);\nvoid HPInit(HP* php);\nvoid HPDestroy(HP* php);\nvoid HPPush(HP* php, HPDataType x);\nvoid HPPop(HP* php);\nHPDataType HPTop(HP* php);\nbool HPEmpty(HP* php);<\/code><\/pre>\n\n\n\n<p>\u7ed3\u6784\u4f53\u91cc\u9762\u4e00\u5171\u5305\u62ec3\u4e2a\u6210\u5458\uff1a\u5b9e\u73b0\u7684\u5806\u7684\u6570\u7ec4\uff0c\u5927\u5c0f\uff0c\u7a7a\u95f4<\/p>\n\n\n\n<p>\u4e0b\u9762\u662f\u5177\u4f53\u51fd\u6570\u7684\u5b9e\u73b0\uff1a<\/p>\n\n\n\n<p>\u6838\u5fc3\u7b97\u6cd5\u5c31\u662f\u5411\u4e0a\u8c03\u6574\u7b97\u6cd5\uff0c\u5411\u4e0b\u8c03\u6574\u7b97\u6cd5\uff1a<\/p>\n\n\n\n<p>void AdjustUp(HPDataType* a, int child)<br>{<br>\/\/ \u521d\u59cb\u6761\u4ef6<br>\/\/ \u4e2d\u95f4\u8fc7\u7a0b<br>\/\/ \u7ed3\u675f\u6761\u4ef6<br>int parent = (child &#8211; 1) \/ 2;<br>\/\/while (parent >= 0)<br>while (child > 0)<br>{<br>if (a[child] < a[parent])<br>{<br>Swap(&#038;a[child], &#038;a[parent]);<br>child = parent;<br>parent = (child &#8211; 1) \/ 2;<br>}<br>else<br>{<br>break;<br>}<br>}<br>}<\/p>\n\n\n\n<p>void HPPush(HP* php, HPDataType x)<br>{<br>assert(php);<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>if (php->size == php->capacity)\n{\n    int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;\n    HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));\n    if (tmp == NULL)\n    {\n        perror(\"realloc fail\");\n        return;\n    }\n\n    php->a = tmp;\n    php->capacity = newcapacity;\n}\n\nphp->a[php->size] = x;\nphp->size++;\n\nAdjustUp(php->a, php->size - 1);<\/code><\/pre>\n\n\n\n<p>}<\/p>\n\n\n\n<p>void AdjustDown(HPDataType* a, int n, int parent)<br>{<br>\/\/ \u5148\u5047\u8bbe\u5de6\u5b69\u5b50\u5c0f<br>int child = parent * 2 + 1;<br>while (child < n) \/\/ child >= n\u8bf4\u660e\u5b69\u5b50\u4e0d\u5b58\u5728\uff0c\u8c03\u6574\u5230\u53f6\u5b50\u4e86<br>{<br>\/\/ \u627e\u51fa\u5c0f\u7684\u90a3\u4e2a\u5b69\u5b50<br>if (child + 1 < n &#038;&#038; a[child + 1] < a[child])<br>{<br>++child;<br>}<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>    if (a[child] < a[parent])\n    {\n        Swap(&#038;a[child], &#038;a[parent]);\n        parent = child;\n        child = parent * 2 + 1;\n    }\n    else\n    {\n        break;\n    }\n}<\/code><\/pre>\n\n\n\n<p>}<\/p>\n\n\n\n<p>\u5411\u4e0b\u8c03\u6574\u7b97\u6cd5\u793a\u610f\u56fe\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"459\" src=\"http:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-37-1024x459.png\" alt=\"\" class=\"wp-image-189\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-37-1024x459.png 1024w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-37-300x135.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-37-768x344.png 768w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-37.png 1231w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\u5411\u4e0a\u8c03\u6574\u7b97\u6cd5\u4e0e\u5176\u7c7b\u4f3c\uff0c\u4e3b\u8981\u7528\u4e8e\u63d2\u5165\u3002<\/p>\n\n\n\n<p>\u4eca\u5929\u5806\u7684\u66f4\u65b0\u5c31\u5230\u8fd9\u91cc\uff0c\u660e\u5929\u4f1a\u66f4\u65b0\u5806\u6392\u5e8f\u53ca\u5176\u5e94\u7528\uff0c\u8c22\u8c22\u5927\u5bb6\u7684\u9605\u8bfb\uff0c\u5982\u6709\u9519\u8bef\uff0c\u6b22\u8fce\u8bc4\u8bba\u533a\u6307\u51fa\uff01\uff01<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4ee5\u4e0b\u4ee3\u7801gitee\u4ed3\u5e93\u5730\u5740tgw\/\u6570\u636e\u7ed3\u6784\u3002 \u5806\u7684\u6982\u5ff5\uff1a\u5982\u679c\u6709\u4e00\u4e2a\u5173\u952e\u7801\u7684\u96c6\u5408K = {k1 \uff0ck2 \uff0ck3 &#8230;<\/p>\n","protected":false},"author":1,"featured_media":188,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_kad_post_classname":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-187","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/187","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=187"}],"version-history":[{"count":4,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/187\/revisions"}],"predecessor-version":[{"id":868,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/187\/revisions\/868"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/media\/188"}],"wp:attachment":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=187"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=187"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}