Remove and return the number with the smallest absolute value from the heap.<\/li>\n<\/ol>\nThe input consists of several commands, with each command being a form of inserting or removing a number. If the heap is empty, it outputs 0.<\/p>\n
Input Format<\/h3>\n
The input is provided over multiple lines, and each line has the following format:<\/p>\n
\n 1\n -1\n 0\n 1\n 2 Ivy\n <\/pre>\nOutput Format<\/h3>\n
For each remove command, output the value at the top of the heap.<\/p>\n<\/section>\n\nProblem Solving Process<\/h2>\n
To solve the problem, we will first define the structure of the absolute value heap and choose a data structure for it. A primary method to implement as a boilerplate is using an array-based heap structure. Here, we will utilize Swift\u2019s basic data structure, Array<\/code>.<\/p>\nStep 1: Designing the Heap Structure<\/h3>\n
To implement an absolute value heap, we need to define the structure and priority of the heap. We will prioritize the absolute value, and for elements with the same absolute value, we will base the priority on the actual number size. To do this, we will use a tuple that adopts the Comparable<\/code> protocol.<\/p>\nStep 2: Implementing Insert Operation<\/h3>\n
When inserting into the heap, we add the new element to the end of the array and then move it up until the heap property is satisfied. This process is called ‘bubbling up’ or ‘up-heap’.<\/p>\n
Step 3: Implementing Delete Operation<\/h3>\n
To delete the element with the smallest absolute value, we remove the root element, place the last element in the root position, and then move it down until the heap property is satisfied. This process is called ‘bubbling down’ or ‘down-heap’.<\/p>\n<\/section>\n\nSwift Code Implementation<\/h2>\n
Now, let’s look at the actual Swift code based on the algorithm we have organized.<\/p>\n
\n import Foundation\n\n struct AbsoluteHeap {\n private var heap: [(value: Int, absolute: Int)] = []\n\n mutating func insert(_ value: Int) {\n let absoluteValue = abs(value)\n heap.append((value, absoluteValue))\n upHeap(index: heap.count - 1)\n }\n\n mutating func pop() -> Int {\n guard !heap.isEmpty else { return 0 }\n let root = heap[0].value\n heap[0] = heap.removeLast()\n downHeap(index: 0)\n return root\n }\n\n private mutating func upHeap(index: Int) {\n var childIndex = index\n let child = heap[childIndex]\n var parentIndex = (childIndex - 1) \/ 2\n\n while childIndex > 0 && (heap[parentIndex].absolute > child.absolute ||\n (heap[parentIndex].absolute == child.absolute && heap[parentIndex].value > child.value)) {\n heap[childIndex] = heap[parentIndex]\n childIndex = parentIndex\n parentIndex = (childIndex - 1) \/ 2\n }\n\n heap[childIndex] = child\n }\n\n private mutating func downHeap(index: Int) {\n var parentIndex = index\n let count = heap.count\n\n while true {\n let leftChildIndex = 2 * parentIndex + 1\n let rightChildIndex = 2 * parentIndex + 2\n var candidateIndex = parentIndex\n\n if leftChildIndex < count && (heap[leftChildIndex].absolute < heap[candidateIndex].absolute ||\n (heap[leftChildIndex].absolute == heap[candidateIndex].absolute && heap[leftChildIndex].value < heap[candidateIndex].value)) {\n candidateIndex = leftChildIndex\n }\n \n if rightChildIndex < count && (heap[rightChildIndex].absolute < heap[candidateIndex].absolute ||\n (heap[rightChildIndex].absolute == heap[candidateIndex].absolute && heap[rightChildIndex].value < heap[candidateIndex].value)) {\n candidateIndex = rightChildIndex\n }\n\n if candidateIndex == parentIndex { break }\n heap.swapAt(parentIndex, candidateIndex)\n parentIndex = candidateIndex\n }\n }\n }\n\n var absoluteHeap = AbsoluteHeap()\n let operations = [1, -1, 0, 1, 2]\n for op in operations {\n if op != 0 {\n absoluteHeap.insert(op)\n } else {\n print(absoluteHeap.pop())\n }\n }\n <\/pre>\n<\/section>\n\nTest Cases<\/h2>\nTest Case 1<\/h3>\n
Input values used in the script: [1, -1, 0, 1, 2]<\/code><\/p>\nExpected output: 1<\/code> (when pop is performed)<\/p>\nTest Case 2<\/h3>\n
Additional input values used in the script: [2, -4, 0]<\/code><\/p>\nExpected output: -4<\/code> (when pop is performed)<\/p>\n<\/section>\n\nConclusion<\/h2>\n
We have now successfully implemented an absolute value heap using Swift. In this tutorial, we utilized the essence of algorithms, carefully chose data structures, and applied basic Swift syntax and structure to implement the heap's insertion and deletion processes. Through this implementation, I hope to solidify your prior knowledge of solving algorithm problems.<\/p>\n
I look forward to solving various algorithm problems together in the future!<\/p>\n<\/section>\n<\/article>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
In this article, we will explore how to implement an absolute value heap using Swift. We will explain in detail the implementation specifics, test cases, and efficiency analysis while solving an algorithm problem. We will look at how to efficiently solve problems using Swift’s capabilities. Problem Description An absolute value heap is a data structure … \ub354 \ubcf4\uae30 “Swift Coding Test Course, Implementing Absolute Value Heap”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[129],"tags":[],"class_list":["post-34834","post","type-post","status-publish","format-standard","hentry","category-swift-coding-test"],"yoast_head":"\nSwift Coding Test Course, Implementing Absolute Value Heap - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34834\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Swift Coding Test Course, Implementing Absolute Value Heap - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"In this article, we will explore how to implement an absolute value heap using Swift. We will explain in detail the implementation specifics, test cases, and efficiency analysis while solving an algorithm problem. We will look at how to efficiently solve problems using Swift’s capabilities. Problem Description An absolute value heap is a data structure … \ub354 \ubcf4\uae30 "Swift Coding Test Course, Implementing Absolute Value Heap"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34834\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:32:31+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:26:20+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34834\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34834\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Swift Coding Test Course, Implementing Absolute Value Heap\",\"datePublished\":\"2024-11-01T09:32:31+00:00\",\"dateModified\":\"2024-11-01T11:26:20+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34834\/\"},\"wordCount\":490,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Swift Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34834\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34834\/\",\"name\":\"Swift Coding Test Course, Implementing Absolute Value Heap - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:32:31+00:00\",\"dateModified\":\"2024-11-01T11:26:20+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34834\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34834\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34834\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Swift Coding Test Course, Implementing Absolute Value Heap\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Swift Coding Test Course, Implementing Absolute Value Heap - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34834\/","og_locale":"ko_KR","og_type":"article","og_title":"Swift Coding Test Course, Implementing Absolute Value Heap - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"In this article, we will explore how to implement an absolute value heap using Swift. We will explain in detail the implementation specifics, test cases, and efficiency analysis while solving an algorithm problem. We will look at how to efficiently solve problems using Swift’s capabilities. Problem Description An absolute value heap is a data structure … \ub354 \ubcf4\uae30 \"Swift Coding Test Course, Implementing Absolute Value Heap\"","og_url":"https:\/\/atmokpo.com\/w\/34834\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:32:31+00:00","article_modified_time":"2024-11-01T11:26:20+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34834\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34834\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Swift Coding Test Course, Implementing Absolute Value Heap","datePublished":"2024-11-01T09:32:31+00:00","dateModified":"2024-11-01T11:26:20+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34834\/"},"wordCount":490,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Swift Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34834\/","url":"https:\/\/atmokpo.com\/w\/34834\/","name":"Swift Coding Test Course, Implementing Absolute Value Heap - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:32:31+00:00","dateModified":"2024-11-01T11:26:20+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34834\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34834\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34834\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Swift Coding Test Course, Implementing Absolute Value Heap"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34834","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34834"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34834\/revisions"}],"predecessor-version":[{"id":34835,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34834\/revisions\/34835"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34834"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34834"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34834"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}